49. Group Anagrams

文字列を含んだ配列が与えられるので、アナグラムが同一の文字列でグルーピングする。

My Answer

時間計算量は $O(n * mlogm)$ 、空間計算量は $O(n * m)$ となった。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for s in strs:
            sorted_s = "".join(sorted(s))
            if sorted_s not in dic:
                dic[sorted_s] = [s]
            else:
                dic[sorted_s].append(s)
        return [dic[s] for s in dic]

与えられた文字列を(アルファベット順に)ソートし、ソートした文字列をKeyとして辞書に格納していく。後は、辞書からそのまま取り出した値を指定の配列の形で返してやればよい。

実行速度は100 msとなり、全体の72.20 %の参加者より速い結果となった。

Best Answer

Categorize by Count

解説のページを見ると、さらによいと思われるアプローチが存在した。アルファベットを0から25の数字に対応付けて、それらの出現回数をカウントしたものをキーとする。

サンプルコードは以下のとおり。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list) 
        for s in strs: # n
            count = [0] * 26 # m
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return ans.values()