49. Group Anagrams

Medium

Description

給定字串陣列 strs，將所有 anagram 分為一組。字串只包含小寫英文字母，回傳順序不限。

Example:

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Intuition#

核心思路：找到 anagram 的「標準化表示」作為 HashMap 的 key，相同 key 的字串歸為同一組。

兩個字串是 anagram <=> 排序後相同 <=> 字元頻率完全相同
關鍵在於如何定義每個 anagram 群組的 key

Approaches#

1: Sort as Key#

概念: 將每個字串排序後作為 key，排序結果相同的字串是 anagram
時間複雜度: O(n * k log k) - n 為字串數量，k 為最長字串長度
空間複雜度: O(n * k) - 儲存所有字串

class Solution {
    fun groupAnagrams(strs: Array<String>): List<List<String>> {
        val map = HashMap<String, MutableList<String>>()
        for (s in strs) {
            val key = String(s.toCharArray().also { it.sort() })
            map.getOrPut(key) { mutableListOf() }.add(s)
        }
        return map.values.toList()
    }
}

⭐2: Character Count as Key#

概念: 用字元頻率陣列的字串表示作為 key，例如 “eat” -> “1#0#0#…#1#…#0#1#0#…"（a=1, e=1, t=1），避免排序
時間複雜度: O(n * k) - n 為字串數量，k 為最長字串長度，計數為線性
空間複雜度: O(n * k) - 儲存所有字串

class Solution {
    fun groupAnagrams(strs: Array<String>): List<List<String>> {
        val map = HashMap<String, MutableList<String>>()
        for (s in strs) {
            val count = IntArray(26)
            for (c in s) count[c - 'a']++
            val key = count.joinToString("#")
            map.getOrPut(key) { mutableListOf() }.add(s)
        }
        return map.values.toList()
    }
}

注意 key 的分隔符號：不能直接拼接數字（如 “1100…” 會產生歧義），必須用分隔符如 # 來區分各字母的計數。

🔑 Takeaways#

Pattern: 分組問題 -> 定義 canonical key + HashMap 歸類
關鍵技巧: 字元頻率作 key 可以將排序的 O(k log k) 降到 O(k)；getOrPut 是 Kotlin 中簡潔處理 Map 預設值的慣用寫法