概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」
Twitterやってます。
技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！
お知らせ
Day 100でQiitaでの投稿はひとまず区切りを付けようかと思います。
タグの記事が僕の記事ばかりになってしまうのもいかがなものかと思いましたし、他に有益な情報を提供している方の邪魔になってしまうこともあると考えたので、こうすることにしました。
至らない部分は多々ありましたが、今までお付き合い頂きありがとうございました。
問題を解いて記事を書く、というのは上記の個人ブログで続けるつもりですし、興味ある方はたまにそちらを覗いていただけると嬉しいです。
Twitterの方のアカウントはほとんど更新通知用と化しているので、Leetcodeを解く記事について気になる方はそちらも合わせてフォローいただくと良いかもしれません。
問題
49. Group Anagrams
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。
問題としてはアナグラムである文字列の入った配列が与えられます。
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解法
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list)
for s in strs:
sorted_word = ''.join(sorted(s))
ans[sorted_word].append(s)
return ans.values()
# Runtime: 92 ms, faster than 98.06% of Python3 online submissions for Group Anagrams.
# Memory Usage: 16.8 MB, less than 71.89% of Python3 online submissions for Group Anagrams.
アナグラムというとハッシュマップを使うと解きやすいと思います。
2つの文字列を比較した時に、文字列を構成する要素が同じ数で揃っていれば良いので、例えば
"abc"と"cab"の場合であればどちらも
aが1回、bが1回、cが1回出現しているので、
a:0,b:0,c:0....といった風にa~zまで全ての個数をハッシュマップで管理すれば特定の文字列がアナグラムであるかを判別することができます。
今回の回答は前から舐めていく過程で一旦ソートすることで、例の配列を以下のように変換しています。
aet
aet
ant
aet
ant
abt
そして、それぞれの要素をソートしていない元の文字列のままansに追加し、そしてvalueのみを返すことできちんと分類されています。
なお、なぜきちんと分類されているか、という点についてですが、最初のdefaultdictで引数にlistを与えているため、[aet],[ant],[abt]という風にリスト化されているためです。
では今回はここまで。
お疲れ様でした。