# LeetCode Easy 49. Group Anagrams

tags: leetcode

問題

• Explore
• Problems

アイデア

文字列の配列が与えられた時，アナグラム(文字の位置を入れ替えて全く同じ文字列になる文字列群)をまとめて二次元配列で返せという問題です．

…これと同じ問題を某社の面接で解かされました(なお前回は解けなかった)

アナグラムはそれぞれの文字の出現回数が同じということに注目すれば良いです．

解法

• 文字列を文字列での文字の出現回数を保存したタプルに変換します(これはPythonがListをキーに出来ないからです)．
• このTupleが連想配列内にあれば，それをキーとするValueを添え字にして，配列内の配列にアクセスして文字列を連結します．
• なければ，新たにその文字列のみを保持する配列を配列内に入れます．
• そして，そのTupleをkeyとして，valueを配列内の要素-1とします．

計算量

文字列の配列の長さを$N$とします．文字列の最大長を$K$とします．

• 時間計算量
  • 文字列を変換するのに$O(K)$必要です．
  • また，文字列を$N$回変換する必要が有ります．
  • トータルで$O(KN)$
• 空間計算量
  • 連想配列で変換した文字列を保管するので，$O(N)$

Python

from typing import Tuple

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def make_string_char_count_tuple(s: str) -> Tuple[int]:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            return tuple(count)
        cache = {}
        res = []
        for s in strs:
            c_count_list = make_string_char_count_tuple(s)
            if c_count_list in cache:
                res[cache[c_count_list]].append(s)
            else:
                res.append([s])
                cache[c_count_list] = len(res) - 1
        return res