始めに
今回はLeetCodeのGroup Anagramsに挑戦してみた
難易度はMediumだけどポイントさえ掴めれば解けるはず
この記事はメガベンを目指すよわよわエンジニアによるものなので間違えがあればビシバシご指摘下さい！
ではやっていこう
今回挑戦した問題
問題
この問題は複数の単語が格納されたstrsという配列をアナグラム毎にグループ分けをする問題。
アナグラムとは文字を入れ替えたら同じ文字列になる単語のことです。
例えば、
abc, cba, bac
↑は文字を入れ替えると全て同じ単語になりますよね
strs = ["abc", "cba", "bac", "tab"]
上記をアナグラム毎に分けると以下のようになる
ans = [[abc, cba, bac], [tab]]
多分直感的に理解できる人が多いけどこれをプログラムにしていくと意外と頭がこんがらがるんよね...
考察
まずこの問題を解く上で重要なのは
- ハッシュマップを使って効率的に解く
- ソートを使い、アナグラム判定ができるようにする
- ハッシュマップの構造を適切な形にする
適切なハッシュマップ構造が作れればほぼ勝ち。
今回の場合で言うと以下の形にできればOK
キーの部分は各単語をソートした値です
# ハッシュマップの中身
{
abc: ["abc", "cba", "bac"],
abt: ["tab"]
}
解法
ではコードを書いていく
まずはハッシュマップを作成していく
defaultdictを使うことで存在しないキーにアクセスしてもエラーにならないので不要なif分を排除できる。
と言っても大きな支障はないから通常の辞書型を使っても問題ないと思う。
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_map = defaultdict(list)
適切なハッシュマップを作成していく
各単語をソートし、ソートした値をハッシュマップのキー設定。
そしてソート前の値をバリューに追加していく。
for word in strs:
sorted_word = "".join(sorted(word))
anagram_map[sorted_word].append(word)
実はここまでで既に目標のハッシュマップ構造にになっている↓
# ハッシュマップの中身
{
abc: ["abc", "cba", "bac"],
abt: ["tab"]
}
適切な形式にして返す
完成したハッシュマップの値のみを配列に格納して返せば完成！
return list(anagram_map.values())
以下は全文です
この問題の計算量はO(n×mlogm) となります。
一般的なfor文でO(N)
sortはO(mlogm)
よってO(n×mlogm)となる訳です。（間違ってたらご指摘お願いします）
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_map = defaultdict(list)
for word in strs:
sorted_word = "".join(sorted(word))
anagram_map[sorted_word].append(word)
return list(anagram_map.values())
まとめ
- アルゴリズムの選定(ハッシュマップ)
- ソートすることでアナグラム判定をしやすくする（アナグラムの性質理解）
- ハッシュマップでソートした値をキーにする(適切なハッシュマップ構造)
上記を問題を読んだ時点で自然と出てくるレベルになればサクッと解ける
ちなみに自分は結構時間かかった...
感想
やってることは今までのハッシュマップ問題と変わりないが、ハッシュマップを適切な形式にするのが少し苦手なのがわかった。
ここら辺は解いた問題数とかで変わってくるのかな？
まあどちらにしてもまだまだ修行が足りないな〜