こんにちは
今回の学びは
文字列の登場回数をもつdictと ソートされた配列は 同じ情報をもつ
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
アナグラム問題はO(N*2)で解いたのでそれを使いまわそう
と思いましたが、
単純にハッシュを文字列化した物をキーとしてリストを作れば簡単だな、とう手法をとりました
O(N*文字列平均)というアルゴリズムですが
ハッシュも文字列化した時必ずしも
ソートされていないことがわかりました。
このテストケースで落ちたのが証拠です
# 1713pm 実装5分ご最初の提出は, 47/101でこける。
# wrong answer of me: [["eat"],["tea"],["tan"],["ate"],["nat"],["bat"]]
# 1716pm 問題は、うまくdictのキーをstr西後きにソートされていないのが原因ですん。
# 多分追加した順になっちゃんか。
(
["eat","tea","tan","ate","nat","bat"],
[["bat"],["nat","tan"],["ate","eat","tea"]]
)
ですので、
半ば無理やりO(nlogn)のソートもってきています。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(nlogN)です
実際の実装はこちら
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = defaultdict(list)
for s in strs:
mp = defaultdict(int)
for i in range(len(s)):
mp[s[i]] += 1
flatten = list(map(lambda kv : (kv[0], kv[1]), mp.items()))
flatten.sort(key=lambda tp: tp[0])
anagrams[str(flatten)].append(s)
return anagrams.values()
実装後です。timespace analysis (時間とスペースの分析）は O(nlogN)です
遅いいので
他の人解答をみて、どのように考えれば、もう少し早くなるか
検討してみます。
わかりやすい。まずは私と同じアルゴリズムですね。書き方は端折ってますが
https://leetcode.com/problems/group-anagrams/discuss/384470/Solution-in-Python-3-(three-lines) これなら１っ分で書けて
いいな。
次、上位３０％の解答
なるほどこちらもO(nlogN)ですが、ちょっとタイミタイミングをヅラしてきています
defaultdictの操作やtupleの配列ソートがなく、だいぶシンプルなんですね。
実は考えてみると
ここで私がやっているハッシュと ソートされた文字列は同じ情報を持ちます。
{a:2, b:1, c:3}というハッシュと
aabcccは
保持している情報としては同じなんです
こういうイメージですね。
これは覚えておきましょう
・文字列の登場回数をもつdictと ソートされた配列は 同じ情報をもつ
他にも
配列は頑張れば、とうかバイナリーサーチはあれで実装されているから二分木構造になっていたり
実は奥が深い。情報を凝縮してくれる場面があると、覚えておこう。
メモリの節約などの実装時には役にたちそう
まとめ
・文字列の登場回数をもつdictと ソートされた配列は 同じ情報をもつ
以上です