給定字串陣列
strs，將所有 anagram 分為一組。字串只包含小寫英文字母，回傳順序不限。
Example:
Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
Intuition
TIP
核心思路：找到 anagram 的「標準化表示」作為 HashMap 的 key，相同 key 的字串歸為同一組。
- 兩個字串是 anagram <=> 排序後相同 <=> 字元頻率完全相同
- 關鍵在於如何定義每個 anagram 群組的 key
Approaches
1. Sort as Key — O(n * k log k) / O(n * k)
- Idea: 將每個字串排序後作為 key，排序結果相同的字串是 anagram
- Time:
O(n * k log k)- n 為字串數量，k 為最長字串長度 - Space:
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 — O(n * k) / O(n * k)
- Idea: 用字元頻率陣列的字串表示作為 key，例如 “eat” -> “1#0#0#…#1#…#0#1#0#…”（a=1, e=1, t=1），避免排序
- Time:
O(n * k)- n 為字串數量，k 為最長字串長度，計數為線性 - Space:
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()
}
}WARNING
注意 key 的分隔符號：不能直接拼接數字（如 “1100…” 會產生歧義），必須用分隔符如 # 來區分各字母的計數。
🔑 Takeaways
- Pattern: 分組問題 -> 定義 canonical key + HashMap 歸類
- Key trick: 字元頻率作 key 可以將排序的 O(k log k) 降到 O(k)；
getOrPut是 Kotlin 中簡潔處理 Map 預設值的慣用寫法