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

投稿日：2019年9月19日

こんにちは

今回の学びは

文字列の登場回数をもつ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)です