いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 49 group anagram

投稿日:

こんにちは

今回の学びは

文字列の登場回数をもつ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) これなら1っ分で書けて

いいな。

次、上位30%の解答

なるほどこちらもO(nlogN)ですが、ちょっとタイミタイミングをヅラしてきています

https://leetcode.com/problems/group-anagrams/discuss/369006/Very-Simple-Python-3-Solution-beating-79.49-with-comments

defaultdictの操作やtupleの配列ソートがなく、だいぶシンプルなんですね。

実は考えてみると

ここで私がやっているハッシュと ソートされた文字列は同じ情報を持ちます。

{a:2, b:1, c:3}というハッシュと

aabcccは

保持している情報としては同じなんです

こういうイメージですね。

これは覚えておきましょう

・文字列の登場回数をもつdictと ソートされた配列は 同じ情報をもつ

他にも

配列は頑張れば、とうかバイナリーサーチはあれで実装されているから二分木構造になっていたり

実は奥が深い。情報を凝縮してくれる場面があると、覚えておこう。

メモリの節約などの実装時には役にたちそう

 

まとめ

文字列の登場回数をもつdictと ソートされた配列は 同じ情報をもつ

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.