面试题 10.02 变位词组(Group Anagrams):排序哈希与计数哈希两种解法的 LeetCode 实战精讲

原创2026-10-13 13:00:511,874 阅读
文章标签:教程示例工程教育

面试题 10.02 变位词组(Group Anagrams):排序哈希与计数哈希两种解法的 LeetCode 实战精讲

本篇技术指南围绕 doocs/leetcode 仓库中 《程序员面试金典(第 6 版)》系列 的「面试题 10.02 变位词组(Group Anagrams)」展开,完整讲解题目约束、暴力解法的性能瓶颈,以及「排序 + 哈希表」与「计数 + 哈希表」两种标准解法的时间复杂度推导与多语言实现,并结合仓库源码逐行印证实际写法。读完本文,你将掌握字母异位词分组问题的完整解题套路,能够在 Python、Java、C++、Go、TypeScript、Swift、Rust 等语言中独立实现,并理解两种解法各自的适用场景。

题目背景与问题定义

本题收录于《程序员面试金典(第 6 版)》第 10 章「排序与查找」,是面试中高频考察的字符串 + 哈希表综合题,题解文档位于 lcci/10.02.Group Anagrams/README.md。

题目要求编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。所谓变位词(Anagram),是指字母相同、但排列不同的字符串,例如 "eat"、"tea"、"ate" 三者互为变位词。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明(题目约束):

  • 所有输入均为小写字母;
  • 不考虑答案输出的顺序。

与经典的 49. 字母异位词分组 相比,本题出自面试原书、题目表述稍有调整,但核心算法完全一致,仓库中两个题目的题解也保持同构,可以相互对照学习。

解题思路:从暴力两两比较到哈希分组

暴力解法的瓶颈

最直接的想法是两两比较字符串是否互为变位词:对每个字符串先排序,再与其余所有字符串比较。这种做法的复杂度约为 O(n2×klog⁡k)O(n^2 \times k \log k),其中 nn 是字符串个数,kk 是单个字符串的最大长度。

当词数较多时(例如 LeetCode 49 中 nn 可达 10410^4),平方级的比较次数会明显拖慢运行速度,显然不是面试中值得给出的答案。

核心洞察:排序后相同的串即为同一组

关键性质是:互为变位词的一组字符串,按照字符字典序排序后得到的是同一个字符串。例如:

  • "eat"、"tea"、"ate" 排序后都是 "aet";
  • "tan"、"nat" 排序后都是 "ant";
  • "bat" 排序后是 "abt"。

因此,把排序后的串当作哈希键(key),同一键下的原串自然成组,完全不需要两两比较。对每个字符串 ss 计算 k = ''.join(sorted(s)) 并追加到 d[k],最后输出 d 的 value 列表即可——用一次 O(klog⁡k)O(k \log k) 的排序换取一次哈希插入。

以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例,遍历结束时哈希表的状况如下:

key value
"aet" ["eat", "tea", "ate"]
"ant" ["tan", "nat"]
"abt" ["bat"]

最后返回哈希表的 value 列表即可,顺序无关紧要(题目已明确不要求输出顺序)。

方法一:排序 + 哈希表

算法步骤清晰而固定,共三步:

  1. 遍历字符串,对每个字符串按照字符字典序排序,得到一个新的字符串;
  2. 以新字符串为 key,[str] 为 value,存入哈希表当中(典型结构为 HashMap<String, List<String>>);
  3. 后续遍历得到相同 key 时,将其加入到对应的 value 当中。

时间复杂度:O(n×k×log⁡k)O(n \times k \times \log k),其中 nn 是字符串数组的长度,kk 是字符串的最大长度。

仓库源码实现

仓库中该方法对应的题解文件为 Solution.* 系列,下面逐一对照:

Python3(Solution.py):

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

defaultdict(list) 省去了「键不存在则先初始化空列表」的判断;sorted(s) 返回字符列表,''.join(...) 将其拼接为排序后的字符串作为键。

Java(Solution.java):

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> d = new HashMap<>();
        for (String s : strs) {
            char[] t = s.toCharArray();
            Arrays.sort(t);
            String k = String.valueOf(t);
            d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(d.values());
    }
}

Java 中字符串不可变,需要先 toCharArray() 转成字符数组排序,再 String.valueOf(t) 还原为字符串键;computeIfAbsent 是 JDK 8+ 的标准写法,等价于「键不存在则创建空列表」。

C++(Solution.cpp):

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> d;
        for (auto& s : strs) {
            string k = s;
            sort(k.begin(), k.end());
            d[k].emplace_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [_, v] : d) ans.emplace_back(v);
        return ans;
    }
};

先复制一份 k = s 再对其排序,避免破坏原串;emplace_back 直接构造避免拷贝;遍历哈希表时用结构化绑定 auto& [_, v] 收集所有分组。

Go(Solution.go):

func groupAnagrams(strs []string) (ans [][]string) {
	d := map[string][]string{}
	for _, s := range strs {
		t := []byte(s)
		sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
		k := string(t)
		d[k] = append(d[k], s)
	}
	for _, v := range d {
		ans = append(ans, v)
	}
	return
}

Go 中字符串转为 []byte 后可用 sort.Slice 按字节排序,再转回字符串;命名返回值 (ans [][]string) 配合裸 return 使代码紧凑。

TypeScript(Solution.ts):

function groupAnagrams(strs: string[]): string[][] {
    const d: Map<string, string[]> = new Map();
    for (const s of strs) {
        const k = s.split('').sort().join('');
        if (!d.has(k)) {
            d.set(k, []);
        }
        d.get(k)!.push(s);
    }
    return Array.from(d.values());
}

split('') 拆成字符数组、sort() 排序、join('') 还原字符串,三步串成一行;d.get(k)! 使用非空断言,因为上面刚 set 过。

Swift(Solution.swift):

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var d = [String: [String]]()
        for s in strs {
            let t = String(s.sorted())
            d[t, default: []].append(s)
        }
        return Array(d.values)
    }
}

Swift 字典下标访问支持 default: 参数,缺失键自动以空数组初始化,写法最简。

Rust(Solution.rs):

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut map = HashMap::new();
        for s in strs {
            let key = {
                let mut cs = s.chars().collect::<Vec<char>>();
                cs.sort();
                cs.iter().collect::<String>()
            };
            map.entry(key).or_insert(vec![]).push(s);
        }
        map.into_values().collect()
    }
}

Rust 中 entry(key).or_insert(vec![]) 是「取或插」的惯用法,into_values() 直接消费哈希表得到所有分组。

方法二:计数 + 哈希表

排序键的缺点是引入了 O(klog⁡k)O(k \log k) 的对数因子。而本题字符集很小——只有 26 个小写字母,因此可以把「排序」替换为「计数」,进一步降低单串处理成本。

具体做法:将每个字符串 ss 中字符及其出现次数作为 key,将字符串 ss 作为 value 存入哈希表。

时间复杂度:O(n×(k+C))O(n \times (k + C)),其中 nn 和 kk 分别是字符串数组的长度和字符串的最大长度,CC 是字符集的大小,本题中 C=26C = 26。每个词从 O(klog⁡k)O(k \log k) 的排序变为 O(k+C)O(k + C) 的线性扫描,分组语义不变。

仓库源码实现

该方法对应的题解文件为 Solution2.* 系列。

Python3(Solution2.py):

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

长度为 26 的计数数组通过 ord(c) - ord('a') 映射到下标;tuple(cnt) 可哈希,直接作为字典键——这是 Python 特有的简洁优势。

Java(Solution2.java):

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> d = new HashMap<>();
        for (String s : strs) {
            int[] cnt = new int[26];
            for (int i = 0; i < s.length(); ++i) {
                ++cnt[s.charAt(i) - 'a'];
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > 0) {
                    sb.append((char) ('a' + i)).append(cnt[i]);
                }
            }
            String k = sb.toString();
            d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(d.values());
    }
}

Java 的 int[] 不能直接作 Map 键,因此将计数结果编码为规范化字符串:只保留出现次数 > 0 的字符,形如 "a2b1c5a3",同一组异位词编码后必然一致。

C++(Solution2.cpp):

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> d;
        for (auto& s : strs) {
            int cnt[26] = {0};
            for (auto& c : s) ++cnt[c - 'a'];
            string k;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i]) {
                    k += 'a' + i;
                    k += to_string(cnt[i]);
                }
            }
            d[k].emplace_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [_, v] : d) ans.emplace_back(v);
        return ans;
    }
};

与 Java 版同样的规范化编码思路,k += 'a' + i 与 k += to_string(cnt[i]) 交替拼接出键。

Go(Solution2.go):

func groupAnagrams(strs []string) (ans [][]string) {
	d := map[[26]int][]string{}
	for _, s := range strs {
		cnt := [26]int{}
		for _, c := range s {
			cnt[c-'a']++
		}
		d[cnt] = append(d[cnt], s)
	}
	for _, v := range d {
		ans = append(ans, v)
	}
	return
}

Go 语言中定长数组 [26]int 天然可作 map 键(切片不行),直接以计数数组本身作为键,无需任何编码转换,是这版实现最优雅的地方。

两种方法对比与选型建议

维度 方法一:排序 + 哈希 方法二:计数 + 哈希
核心思想 排序后的字符串作为键 字符频次作为键
单串开销 O(klog⁡k)O(k \log k) O(k+C)O(k + C),C=26C=26
总体复杂度 O(n×k×log⁡k)O(n \times k \times \log k) O(n×(k+C))O(n \times (k + C))
键的形式 排序字符串(如 "aet") 频次数组 / 编码串
额外空间 哈希表,O(nk)O(nk) 每串一个长度 26 的计数,O(nk)O(nk)
代码简洁度 各语言写法最统一 依赖语言对「数组作键」或元组的支持

选型建议:

  • 若追求思路直观、各语言实现一致,选方法一,它是面试中最容易讲清楚的标准答案;
  • 若字符集固定且很小(如本题 26 个小写字母)、字符串普遍较长,方法二在理论上更优;尤其 Go 语言可用 [26]int 直接作键,Python 可用 tuple(cnt),实现成本极低;
  • 需要注意:方法二依赖字符集可枚举。若输入可能包含任意 Unicode 字符,频次数组的规模将不可控,此时应回退到方法一。

两种方法的时间复杂度均已由题解文档给出并得到源码验证:方法一为 O(n×k×log⁡k)O(n \times k \times \log k),方法二为 O(n×(k+C))O(n \times (k + C)),C=26C = 26。

仓库实现与延伸阅读

在 doocs/leetcode 仓库中,本题的完整素材如下,可供继续深入:

总结

「变位词组」一题考察的核心是如何为「字母相同、排列不同」这一等价关系构造稳定的哈希键:

  1. 排序法:利用「变位词排序后相等」的性质,用排序串作键,单串 O(klog⁡k)O(k \log k);
  2. 计数法:利用「字符集有界(26 个小写字母)」的性质,用频次作键,单串 O(k+C)O(k + C)。

两种解法都能在 O(n)O(n) 趟扫描内完成全部分组,空间复杂度均为 O(nk)O(nk) 量级(哈希表总容量)。掌握「先构造规范形、再哈希分组」这一模式,不仅能 AC 本题与 LeetCode 49,还能迁移到「单词频次统计」「同义词合并」等一系列字符串分组问题中。

登录后查看全文
leetcode