vvrf / DSA.log

问题拆解

把字符串数组中互为字母异位词的分到一组。异位词的定义是字母及其出现次数完全相同、只是排列不同，比如 "eat"、"tea"、"ate"。

朴素做法是两两比较：判断两个词是否异位需要 O(k)，配对有 O(n²) 对，而且判出“a 和 b 是一组、b 和 c 是一组”后还得维护并查集式的归并，又慢又绕。

分组问题的通用解法是找一个“同组当且仅当相等”的标签，然后按标签进哈希表。对异位词来说，这个标签唾手可得：把字母排个序，"eat"、"tea"、"ate" 都变成 "aet"。排序抹掉了排列的差异，只留下“有哪些字母、各几个”这一本质信息。

一组等价的对象里选一个统一的代表，叫作规范形式（canonical form）。判断“是否等价”从此退化为判断“规范形式是否相等”,而相等判断正是哈希表最擅长的事。

排序后的串作哈希键

一趟遍历：每个词排序得到键，追加到哈希表里对应的组，最后收集所有组。

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars); // 排序后的串是规范形式
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))  # 排序后的串是规范形式
        groups[key].append(s)
    return list(groups.values())

func groupAnagrams(strs []string) [][]string {
    groups := map[string][]string{}
    for _, s := range strs {
        b := []byte(s)
        slices.Sort(b)
        key := string(b) // 排序后的串是规范形式
        groups[key] = append(groups[key], s)
    }
    res := make([][]string, 0, len(groups))
    for _, g := range groups {
        res = append(res, g)
    }
    return res
}

use std::collections::HashMap;

pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut groups: HashMap<Vec<u8>, Vec<String>> = HashMap::new();
    for s in strs {
        let mut key = s.clone().into_bytes();
        key.sort_unstable(); // 排序后的串是规范形式
        groups.entry(key).or_default().push(s);
    }
    groups.into_values().collect()
}

注意进组的是原字符串，键只是路标——初学者偶尔会把排序后的串存进组里，输出就全变成 "aet" 了。哈希表的 value 直接用列表累积，省去“先查组号再定位”的二段跳。

计数签名作键

如果单词很长，排序的 O(k log k) 可以再省：字母表只有 26 个小写字母，统计每个字母的出现次数得到一个长度 26 的计数数组，它同样是异位词的规范形式，而且 O(k) 就能算出来。

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        String key = Arrays.toString(count); // 计数签名，如 [1, 0, 2, ...]
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        groups[tuple(count)].append(s)  # 元组可哈希，直接作键
    return list(groups.values())

func groupAnagrams(strs []string) [][]string {
    groups := map[[26]int][]string{}
    for _, s := range strs {
        var count [26]int // 数组（非切片）可作 map 键
        for i := 0; i < len(s); i++ {
            count[s[i]-'a']++
        }
        groups[count] = append(groups[count], s)
    }
    res := make([][]string, 0, len(groups))
    for _, g := range groups {
        res = append(res, g)
    }
    return res
}

use std::collections::HashMap;

pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut groups: HashMap<[u8; 26], Vec<String>> = HashMap::new();
    for s in strs {
        let mut count = [0u8; 26]; // 定长数组实现了 Hash，可作键
        for &b in s.as_bytes() {
            count[(b - b'a') as usize] += 1;
        }
        groups.entry(count).or_default().push(s);
    }
    groups.into_values().collect()
}

这个版本的坑全在“键的可哈希性”上：Python 的 list 不可哈希，要转成 tuple；Go 的切片不能作 map 键，定长数组 [26]int 才可以；Java 没有值语义的数组相等，得把计数数组序列化成字符串。千万不要把计数简单拼接成 "1012" 这种不带分隔符的串——[1, 0, 12] 和 [10, 1, 2] 会撞在一起，要么用 Arrays.toString 这种自带分隔符的形式，要么手动插入分隔符。本题单词不长，排序版通常就够快，计数版胜在思路可扩展。

复杂度

指标	复杂度	原因
时间	`O(n · k log k)`	每个词排序 O(k log k)；计数版为 O(n · k)
空间	`O(n · k)`	哈希表存全部字符串及其键

可以迁移的模式

分组、去重、判等价，先问一句：这类对象的规范形式是什么？
规范形式可以是排序结果、计数签名，也可以是任何“等价则必相同”的映射；
用复合结构当哈希键时，先确认它在该语言里可哈希、且按值比较。

“把等价类映射到同一个键”是哈希分组的心法，判定异位词、同构字符串、轮转字符串归一化，全是同一招。