ゼロから始めるLeetCode Day93 「49. Group Anagrams」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」

次回
まだ

Twitterやってます。

問題

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]という風にリスト化されているためです。

では今回はここまで。
お疲れ様でした。