示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以开源仓库 doocs/leetcode 中 lcci/10.02.Group Anagrams 一题的英文题解文档README_EN.md为核心系统讲解《程序员面试金典第 6 版》面试题 10.02「变位词组」的两类主流解法——排序键哈希法与计数键哈希法并给出 Python、Java、C、Go、TypeScript、Swift、Rust 等多语言的可运行实现。读完本文你将掌握用规范化键canonical key聚类等价字符串这一哈希表核心技巧并能独立推导出时间复杂度分析直接应用于 LeetCode 49. Group Anagrams 等同源题目。题目背景与题意理解本题出自《程序员面试金典第 6 版》面试题 10.02在 LeetCode 上的编号为 group-anagrams-lcci。题目要求编写一种方法对字符串数组进行排序将所有变位词anagram组合在一起。所谓变位词是指字母相同、但排列不同的字符串例如eat、tea、ate三者互为变位词。给出的示例输入与输出如下Input: [eat, tea, tan, ate, nat, bat] Output: [ [ate, eat, tea], [nat, tan], [bat] ]题目附带两条说明所有输入均为小写字母all inputs will be in lowercase这意味着字符集固定为 26 个字母是方法二能够成立的前提不考虑答案输出的顺序the order of your output does not matter因此直接返回哈希表的value列表即可无需额外排序。题解文档同时提醒本题相对原书题目稍作修改原文 This problem is slightly different from the original one the book主要体现在输入约束与输出格式的规范化上核心算法逻辑与原书一致。解法一排序 哈希表排序键这是题解文档给出的第一种方法也是面试中最容易想到、最稳妥的方案。其核心思想是互为变位词的字符串按字符字典序排序后必然得到同一个字符串因此可以把排序后的字符串作为哈希表的键把原字符串收集到对应的值列表中。算法步骤题解文档将流程拆解为三步遍历字符串数组对每个字符串按照字符字典序排序得到一个新的字符串以新字符串为key、[str]为value存入哈希表HashMapString, ListString中后续遍历遇到相同key时把当前字符串追加到对应的value列表即可。以strs [eat, tea, tan, ate, nat, bat]为例遍历结束时哈希表的状态如下keyvalueaet[eat, tea, ate]ant[tan, nat]abt[bat]最终返回哈希表的value列表即得到分组结果。为什么不用两两比较题解文档在思考部分特别点出了朴素做法的代价如果对每一对字符串都做变位词判断两两比较排序结果时间复杂度为 $O(n^2 k)$其中 $n$ 为字符串个数、$k$ 为字符串最大长度在词数较多时明显偏慢。而排序键方案把两两比较降维为一次性归组每个词只做一次 $O(k \log k)$ 的排序换来一次哈希插入整体只需 $O(n \times k \times \log k)$并且完全避免了嵌套循环。多语言实现题解文档为该方法提供了 Python3、Java、C、Go、TypeScript、Swift 六种实现仓库对应目录 lcci/10.02.Group Anagrams 下还有可独立运行的 Solution.rsRust 版。逐一展开Python3class 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())sorted(s)返回字符列表.join(...)拼回字符串作为键defaultdict(list)保证首次遇到某个键时自动初始化为空列表避免手动判断。Javaclass Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString 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()); } }computeIfAbsent是 Java 中取或建的标准写法键不存在时先创建ArrayList再执行add代码比get/containsKey分支更简洁。Cclass Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring d; for (auto s : strs) { string k s; sort(k.begin(), k.end()); d[k].emplace_back(s); } vectorvectorstring ans; for (auto [_, v] : d) ans.emplace_back(v); return ans; } };这里先拷贝k s再原地sort避免修改原字符串emplace_back直接构造元素减少一次拷贝结构化绑定auto [_, v]遍历键值对。Gofunc 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 }将字符串转为[]byte后排序再转回字符串map[string][]string直接以append维护分组。TypeScriptfunction groupAnagrams(strs: string[]): string[][] { const d: Mapstring, 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()); }JS/TS 中没有现成的字符串排序 APIsplit()拆成字符数组、sort()排序、join()拼回三段式是标准写法Map上需要先has/set初始化再push。Swiftclass 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 的String.sorted()直接返回排序后的字符数组String(...)包回字符串字典下标d[t, default: []]提供了类似defaultdict的默认值语义。Rust仓库额外提供了 Rust 实现 Solution.rsuse std::collections::HashMap; impl Solution { pub fn group_anagrams(strs: VecString) - VecVecString { let mut map HashMap::new(); for s in strs { let key { let mut cs s.chars().collect::Vecchar(); cs.sort(); cs.iter().collect::String() }; map.entry(key).or_insert(vec![]).push(s); } map.into_values().collect() } }entry(key).or_insert(vec![])对应 Java 的computeIfAbsent是 Rust 中取或建惯用法最后into_values()消费掉键直接取出分组列表。复杂度分析设 $n$ 为字符串数组的长度、$k$ 为字符串的最大长度。对每个字符串排序的开销为 $O(k \log k)$遍历全部 $n$ 个字符串后总时间复杂度为 $O(n \times k \times \log k)$哈希表的空间开销为 $O(n \times k)$存储所有字符串及其键。解法二计数 哈希表计数键排序键方案虽直观但每次排序的 $O(k \log k)$ 因子在字符集很小时可以进一步压缩。题解文档给出的第二种方法——计数法正是针对这一点的优化既然题目限定输入全部是小写字母$C 26$就可以把每个字符串中 26 个字母的出现次数统计出来用这个频次向量或其编码字符串作为键。两个字符串互为变位词当且仅当它们的频次向量完全相同。算法思想题解文档的表述是将排序部分改为计数——把每个字符串 $s$ 中的字符以及出现的次数作为key把字符串 $s作为value 存入哈希表。这样避免了每次 $O(k \log k)$ 的排序每个单词的开销降为 $O(k C)$其中 $C$ 是字符集大小本题中 $C 26$。总时间复杂度为 $O(n \times (k C))$当单词长度 $k$ 较大、字符集 $C$ 较小时相对排序键方案有明显优势。多语言实现计数法在题解文档中提供了 Python3、Java、C、Go 四种实现仓库对应目录下还有 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go 可独立运行。逐一展开Python3class 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())ord(c) - ord(a)把字母映射到0~25的下标Python 的list不可哈希因此必须转成tuple(cnt)才能作为字典键——这是本实现最关键的细节。Javaclass Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString 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键会按引用比较而非内容比较因此这里将频次向量编码为字符串遍历 26 个下标只把出现次数大于 0 的字母与次数拼进StringBuilder例如eat编码为a1e1t1、tan编码为a1n1t1。Cclass Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring 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); } vectorvectorstring ans; for (auto [_, v] : d) ans.emplace_back(v); return ans; } };与 Java 版同理用字母次数的紧凑字符串作为键避免使用无法作为unordered_map键的定长数组从源码结构看若要在 C 中直接以数组为键需改用std::arrayint, 26这类可哈希包装类型。Gofunc 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在 Go 中是可比较、可哈希的map[[26]int][]string天然成立代码最为简洁——这一点也解释了为什么各语言需要采用不同的键编码策略。与 LeetCode 49. Group Anagrams 的关联本题与 LeetCode 原题 49. Group Anagrams 同源英文题解文档也注明了题目编号与链接。在仓库中solution/0000-0099/0049.Group Anagrams/README_EN.md 给出了更完整的问题约束1 strs.length 10^4、0 strs[i].length 100、输入仅含小写英文字母且提供了更多边界示例如[]应输出[[]]。这一数据规模恰好验证了题解文档的判断$n \le 10^4$ 时两两比较的 $O(n^2 k)$ 不可行而两种哈希键方案都只需线性扫描加常数级排序/计数完全在限制之内。仓库在 0049.Group Anagrams 目录下同样维护了Solution与Solution2两套多语言实现可作为本题的交叉验证与练习材料。两种方法的对比与选型维度方法一排序键方法二计数键键的构造对字符串做字典序排序统计 26 个字母的频次每个单词开销$O(k \log k)$$O(k C)$$C 26$总时间复杂度$O(n \times k \times \log k)$$O(n \times (k C))$空间复杂度$O(n \times k)$$O(n \times k)$对字符集的依赖无任意字符集均适用依赖输入仅含小写字母这一前提键的编码难度各语言一致无需特殊处理需要语言层面的数组哈希支持或编码技巧选型建议通用性优先时选方法一。它对字符集没有假设任意字符串集合含大写字母、数字、Unicode都能正确分组代码在各语言间写法高度一致面试中作为首选答案最稳妥性能优先时选方法二。在本题全小写的约束下计数法去掉了排序因子当单词很长$k$ 大而词数 $n$ 不多时$O(k C)$ 对 $O(k \log k)$ 的优势更明显方法二在实现时要格外注意语言差异Python 需要tuple(cnt)使列表可哈希Java/C 需要把频次编码成字符串而 Go 可以直接使用[26]int数组作为 map 键——这是本方法最容易写错、也最能体现语言功底的地方。仓库资源速览本题中文题解lcci/10.02.Group Anagrams/README.md本题英文题解本文依据的主体文档lcci/10.02.Group Anagrams/README_EN.md方法一实现Python Solution.py、Java Solution.java、C Solution.cpp、Go Solution.go、TypeScript Solution.ts、Swift Solution.swift、Rust Solution.rs方法二实现Python Solution2.py、Java Solution2.java、C Solution2.cpp、Go Solution2.go同源原题LeetCode 49solution/0000-0099/0049.Group Anagrams/README.md 及其英文版 README_EN.md内含更完整的数据约束与额外边界用例题解总表lcci/README.md快速检索《程序员面试金典》系列全部题目综上变位词组一题的精髓并不在于复杂的算法设计而在于识别出等价类并为其设计规范化键无论是排序得到的规范串还是计数得到的频次向量本质都是把字母相同、排列不同的模糊关系映射为完全确定的哈希键。掌握这一思维模式后同类问题如判断两个字符串是否互为变位词、统计一组字符串中字母组成相同的子集都可以迎刃而解。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐面试题 10.02 变位词组Group Anagrams排序哈希与计数哈希两种解法的 LeetCode 实战精讲面试题 10.02 变位词组Group Anagrams排序哈希与计数哈希两种解法的 LeetCode 实战精讲 本篇技术指南围绕 doocs/leetc示例工程教程LeetCode 49 字母异位词分组Group Anagrams——哈希表分组解法与多语言实现详解LeetCode 49 字母异位词分组Group Anagrams——哈希表分组解法与多语言实现详解 导读 本文讲解 LeetCode 第 49 题字母异科学计算LeetCode-Go 题解 | 49. Group Anagrams字母异位词分组的「排序 哈希」解法LeetCode Go 题解 | 49. Group Anagrams字母异位词分组的「排序 哈希」解法 本文以 LeetCode Go 仓库中 49.示例工程上一篇GoogLeNet 含并行连结的网络Inception详解从原理到多框架动手实现下一篇Univer 线程评论体系解析univerjs/thread-comment 共享模型、命令与服务实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考