概要
-
LeetCode を始めてみた。
せっかくなので１テーマごとに解法と学びをアウトプットしてみる。
取り組む内容
- こちらのロードマップ に沿って実施する。
- 言語は Python
- 今回テーマは「Arrays & Hashing の Group Anagrams」
テーマ詳細
原文
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
日本語訳
※G 翻訳
文字列 strs の配列を指定して、アナグラムをグループ化します。 回答は任意の順序で返すことができます。 アナグラムは、通常は元の文字をすべて 1 回だけ使用して、別の単語またはフレーズの文字を再配置することによって形成された単語またはフレーズです。
解法
class Solution(object):
def groupAnagrams(self, strs):
"""
strs: List(str)
return: List(List(str))
"""
h = {}
for word in strs:
sorted_word = "".join(sorted(word))
if sorted_word not in h:
h[sorted_word] = [word]
else:
h[sorted_word].append(word)
answer = []
for i in h.keys():
answer.append(h[i])
return answer
結果
- Runtime:63ms
- Beats 87.25% of users with Python ※投稿日時点
思想
- 所見では解けなかったので、先人のSolutionを参考にさせていただきました
- アナグラムはソートすると同じ文字列になる性質があるのでそれを利用する
- ソート後の文字列と、ソート前の文字列が対応するように管理する。管理方法は辞書で実施することに
- 辞書のkeyにソート後、valueにソート前の文字列を持たせる。後者はリスト型にする。Dict(str:List(str))
学び
- 「アナグラムはソートすると同じ文字列になる性質がある」ということを先人Solutionで見かけて目からウロコだった
- for文の中で以前に出てきた値を記憶しておきたい場面は頻繁にあると思おうが、その際には辞書型が有用な解決策となる。個人的に辞書はあまり使用する
- sorted("tea")で ["a", "e", "t"]というリストで返ってくる。これを["aet"]に変形するには"".join(sorted("tea"))とjoinを使用するとできる
- str in {辞書}とすると 辞書のkeyの中にstrが含まれるかどうかが判定される
感想
- 初めてのmediumレベルだった。その通りで難しく所見では解けなかった
- アナグラムの見分け方として、「アナグラムはソートすると同じ文字列になる性質がある」この考え方はとても効率的だし、コードに落としても分かりやすいので良い学びになった