🖋

LeetCode 49. Group Anagrams (Python3)

に公開
Python
LeetCode
tech

はじめに

LeetCode 「49. Group Anagrams」の問題を Python3 で解きました。

問題

https://leetcode.com/problems/group-anagrams/description/

問題文

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

和訳
文字列の配列strsが与えられた場合、アナグラムをグループ化します。答えは任意の順序で返して構わない。

例

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Input: strs = [""]

Output: [[""]]

Input: strs = ["a"]

Output: [["a"]]

制約

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

解答1

単語の配列から、アナグラムをグループ化する問題です。

同じグループに属する単語たちは、同じ特徴（キー）を持っているはずです。
そのキーをソートした文字列として表現することができます。

例えば：

  • "eat" → "aet"
  • "tea" → "aet"
  • "ate" → "aet"

同じ "aet" というキーでまとめられるため、アナグラム同士をグループ化できます。

コード

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)
        return list(groups.values())

計算量

  • 時間的計算量：O(n * m log m)
    • 各文字をソートするのに O(m log m) (mは単語の長さ)
    • これをn個の単語に対して行う
  • 空間的計算量：O(n * m)

解答2

次に、文字の出現回数をキーとする方法です。

アルファベットは 26 種類しかないので、各文字の出現回数を記録した長さ 26 の配列を作ります。
これをタプルに変換すれば、ソートせずにキーとして利用できます。

コード

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

count = [0] * 26 でアルファベット用の配列を用意します。
単語を1文字ずつcount[ord(ch) - ord('a')] += 1で出現した文字に対応するインデックスの値を+1します。
ordは1文字のunicodeコードポイントを示す整数を返します。

例：

  • 文字がa: ord(ch) - ord('a') = 0
  • 文字がe: ord(ch) - ord('a') = 4

計算量

  • 時間的計算量：O(n * m)
    • 各単語で文字をカウントするのにO(m)
    • これをn個の単語に対して行う
  • 空間的計算量：O(n * m)
GitHubで編集を提案

Discussion