企业官网建设流程全解析

3月20号晚上，我照例打开算法在线题库，点开了第49题"字母异位词分组"，标签挂的是哈希。研一课业不算轻松，论文方向还没完全定，刷题更多像是一种保持手感的方式。但这道题做完之后，我没忍住多花了一整个晚上，把两种主流解法和各种边界情况都过了一遍——因为这道题几乎覆盖了哈希表在字符串分类问题里的全部核心用法，非常典型。

如果你也在刷题，或者正在准备面试，这篇内容值得你花十分钟读一遍。我会从最暴力的两两对比讲起，一步步拆到排序归一和计数归一两种哈希方案，把时间复杂度、空间复杂度、容易踩的坑全部过一遍，最后再把这道题的逻辑延伸到几道经典姊妹题上。整篇不堆概念，全是能直接落地的思路和代码。

1. 拆题：字母异位词分组到底在考什么

1.1 题目定义：先搞懂"异位词"的本质

题目给的是一个字符串数组，要求把互为字母异位词的字符串放到同一个组里。

什么叫字母异位词？简单说就是两个单词包含的字母种类和数量完全相同，只是排列顺序不同。比如"ate"、"eat"、"tea"，三个词都包含一个a、一个e、一个t，只是顺序不一样，它们就是一组异位词。反过来，"abc"和"abd"虽然只差一个字母，但根本不是异位词。

这个定义很容易理解，但真正做题的时候，大多数人会在"怎么判断一堆单词是不是同一组"这一步卡住。因为字符串长度不固定，字母组合又千变万化，两两比较除非有特别的技巧，否则复杂度很容易爆炸。

1.2 分组本质：找一个"同一类"的标识

我刷题有个习惯，拿到一道题先不急着写代码，而是先问自己：这道题在考什么抽象能力？

"分组"这件事，本质上是要找到一个标识（key），让同一组的东西拥有相同的标识，不同组的东西拥有不同的标识。这个思想其实我们在生活里天天用。比如快递驿站按取件码分组，一个取件码对应一个货架格子；又比如图书馆按索书号把书放到同一个书架，同一个索书号的书永远在一起。

放在这道题里，就变成了：能不能从每个字符串里算出一个"字母指纹"，让互为异位词的字符串算出来的指纹完全相同，不是异位词的指纹一定不同？

一旦想明白这一步，题目的难度就降了一大半。剩下的问题只有一个：这个"指纹"怎么算？

哈希表在这里恰好是天然的工具。HashMap或者Python里的dict，核心逻辑就是"一个 key 对应一个 value 列表"，遍历所有字符串，算出每个字符串的 key，然后key -> 原字符串往里塞，最后把 value 列表全部取出来就是分组结果。

所以这道题表面上叫"字母异位词分组"，实际上考察的候选方案围绕着一个点：构造 key 的规则。规则选好了，代码写起来十分钟都用不到。

2. 暴力解法为什么会被嫌弃：两两对比的复杂度困境

2.1 最直觉的思路：每两个字符串判断一次

很多接触算法不久的朋友，第一反应一定是：把所有字符串两两都比一遍，互为异位词的就拉进同一个组。

判断两个字符串是否互为异位词，也有两种常见办法：要么把两个字符串排序后比较是否相等，要么统计两个字符串的字母频次后比较频次数组是否一致。两种办法都没错，单独判断一对字符串的时间复杂度是O(k log k)（排序法）或者O(k)（计数法），其中k是字符串平均长度。

伪代码大概长这样：

for i in range(n): for j in range(i+1, n): if 判断(i, j) 互为异位词: 把 j 加入 i 所在的组

看起来很简单，但问题出在循环嵌套上。

2.2 复杂度账本：为什么 n 一到几百就卡住

假设总共有n个字符串，每个平均长度是k，两两比较的循环次数是C(n, 2)，约等于n²/2。如果每次用排序法判断，总复杂度是O(n² k log k)。

套个具体数字感受一下。假设n = 1000，k = 10，那一共要比较约50万对字符串，每对还要排序，实际运算量大概在千万级。看起来好像还能忍？但如果面试官把数据范围加大到n = 10^4，k = 100，那运算量直接飙到上亿 × 排序开销，基本等于超时。

这种暴力的做法还有一个更本质的缺陷：它每次比较都只利用了局部信息，没有把"整个数组里有哪些等价类"这个全局信息提取出来。等于每次都在问"你和他是同一组吗"，而不是"你们共同属于哪个组"。

所以暴力解不是错，而是思路没到位的体现。只要把问题抽象成"找一个全局标识"，解法自然就浮出来了。

3. 排序归一：最直观的哈希键构造法

3.1 为什么"排序后的字符串"能当指纹

这是全网题解里出现频率最高的解法，也是我强烈建议你第一个掌握的解法。

原理一句话就能说清：互为字母异位词的两个字符串，把各自字母按字典序排好之后，得到的结果字符串完全相同。

比如"ate"、"eat"、"tea"，三个都排成"aet"。而"apple"和"aple"长度都不一样，排序后一个是"aelpp"，一个是"aelp"，直接区分开。

为什么这个性质成立？因为排序本质上是在做"多重集合的比较"。检查异位词只看每个字母出现几次，不看顺序；排序把所有字母按统一顺序排列，就相当于把"顺序信息"全部抹掉，只保留"种类和数量信息"。这一点和哈希表的"将输入映射到固定值"天然契合。

3.2 核心代码：Python 实现排序归一

from typing import List from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: groups = defaultdict(list) for word in strs: key = "".join(sorted(word)) groups[key].append(word) return list(groups.values())

整个解法就这么几行，核心操作是sorted(word)。

这里有几个细节值得单独说：

• sorted(word)返回的是一个字符列表，比如sorted("eat")得到['a', 'e', 't']。这个列表本身是可变对象，不能直接作为 dict 的 key（Python 会报TypeError: unhashable type: 'list'），所以必须用"".join(...)变回字符串。
• 选defaultdict(list)而不是普通 dict，是为了省掉每次if key not in groups: groups[key] = []的判断。代码更短，可读性也更好。
• 如果题目输入的单词包含大写字母或者数字，sorted依然能用，因为它是按 Unicode 码位排序。但这道题默认输入都是小写字母，直接用即可。

3.3 复杂度分析和适用范围

排序法的时间复杂度是O(n * k log k)，其中n是字符串个数，k是字符串平均长度。每个字符串都要做一次排序，这是开销的大头。空间复杂度是O(n * k)，因为哈希表里要存所有字符串的原样拷贝。

这套解法写起来最快、最好理解，哪怕你之前完全没见过这道题，在面试现场推五分钟也能推出来。它唯一的软肋是：当单个字符串特别长（比如k达到几千上万）的时候，排序开销会比较扎眼。不过普通面试题里，字符串长度一般不会特别夸张，所以排序法绝对够用。

4. 计数归一：把频次数组做成哈希键

4.1 思路升级：用字母频次代替排序

排序法的思路是"抹掉顺序信息，保留字母集合"。那有没有更直接的方式？有——直接统计每个字母出现了几次，把这个统计结果作为 key。

因为题面通常明确说明字符串只包含小写字母，所以字符集大小是固定的 26。我们完全可以为每个单词建一个长度为 26 的频次数组freq[26]，遍历单词，freq[ord(ch) - ord('a')] += 1。

互为异位词的两个单词，频次数组必然完全一致；不是异位词的两个单词，至少有一个字母出现次数对不上，频次数组必然不一样。所以这个数组天然就是一个合格的"指纹"。

这个思路比排序更贴近问题的本质：异位词的判定本来就只依赖频率，排序是绕了一圈去比较频率，计数法是直接算频率。

4.2 key 的构造细节：Tuple 还是拼接字符串

频次数组本身不能直接当 key，因为 list 是可变对象，Python 的 dict 要求 key 必须是可哈希的不可变对象。于是出现两种常见的构造方式。

第一种是转成 tuple：

from typing import List from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: groups = defaultdict(list) for word in strs: freq = [0] * 26 for ch in word: freq[ord(ch) - ord("a")] += 1 key = tuple(freq) groups[key].append(word) return list(groups.values())

tuple([1, 0, 0, ...])是长度为 26 的整数元组，不可变，可以直接作为 key。两个异位词的频次数组相同，转出来的 tuple 也相同。这种写法在 Python 里最直接，性能也很好。

第二种是转成拼接字符串，比如"a2b1c3"，表示a出现 2 次、b出现 1 次、c出现 3 次。这种写法在 Java、C++ 等语言里更常见，因为那些语言的常见容器不直接支持"把数组当 key"。

比如 Java 写法：

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { cnt[c - '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 key = sb.toString(); map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); } }

注意一个非常关键的细节：拼接的时候一定要带上字母本身，比如"a2b1c3"，而不是直接拼数字"213"。直接拼数字会出现歧义：字符串"abc"的频次是[1, 1, 1]，如果拼成"111"，那和"aaa"的频次[3, 0, 0]拼出来的"300"虽然不一样，但"aa"的[2, 0]和"b"的[0, 1]在某些拼法下可能产生意外撞车。带字母的拼接方式完全杜绝了这类歧义，因为每个数字前都有明确的字母标识。

4.3 复杂度优化：从 O(n k log k) 到 O(n k)

计数法的优势在复杂度上非常直观。每个字符串只需遍历一遍统计 freq，再遍历一次 26 个位置转成 key（数组长度固定 26，与 k 无关），所以总时间复杂度是O(n * (k + 26))，也就是O(n * k)。空间复杂度依然是O(n * k)，因为同样要存所有字符串。

排序法的时间是O(n * k log k)，在k比较大的时候，计数法的优势会越来越明显。这也是面试中非常加分的性能优化点。

两种方法的对比整理一下：

5. 实测体验与容易被坑的细节

5.1 两种方法跑同一组数据时的直观差异

理论归理论，实际用一组数据跑一下更有说服力。我随便造了一组测试：10 万个随机长度在 50 到 100 之间的字符串，字母全部小写。

排序法和计数法在我的本机上都很快，排序法大概在 200 多毫秒，计数法大概在 70 多毫秒。这个差距在普通题目的数据范围内并不致命，但一旦数据量再翻几倍，或者单个字符串长度变大，差距就会被放大。所以我的建议很明确：如果你时间充裕，优先写计数法；如果是在面试高压环境下，先写排序法保底，再提计数法优化。

5.2 刷题时踩过的几个坑

这道题看着简单，但实际写的时候有几个细节特别容易出问题，我自己都踩过，列出来给你们避雷。

坑一：sorted返回的是 list，直接当 key 会报错

很多新手（包括当年的我）写完key = sorted(word)直接塞进 dict，然后看到TypeError: unhashable type: 'list'。原因就是 list 可变、不可哈希。解决办法是"".join(sorted(word))，把它变回字符串。这个错误几乎每个人都会遇到一次，遇到之后印象就深了。

坑二：直接用Counter当 key

Python 的collections.Counter很好用，统计频次只要一行。但Counter是 dict 的子类，同样是可变对象，也不能直接作为 key。如果你真的想用Counter构造 key，需要转成frozenset(counter.items())，但这样反而绕了远路。实际刷题时直接用数组手动统计就够了，性能和可读性都更好。

坑三：拼接频次字符串时省掉字符标识

我在 4.2 里已经强调过，拼接 key 时一定要是"a2b1"这样带字母的格式，不能只拼数字。一旦拼成纯数字，不同频次组合可能产生同一个 key，导致原本不同组的单词被错误合并。这类 bug 非常隐蔽，因为小数据测试不一定能碰到，大规模数据才爆发。

坑四：边界输入[""]和[]

输入是空字符串列表时，正解应该返回[[""]]。排序法里空字符串排序后还是空字符串，可以正常作为 key；计数法里 freq 全是 0，tuple 是 26 个 0，也正常。但如果题目给的输入是空数组[]，返回值应该是空数组[]，不是[[]]。这两个边界我建议写代码的时候顺手测一下，别等提交之后被测试数据教做人。

5.3 面试时候的答题顺序建议

如果你是在面试现场遇到这题，我个人推荐的答题节奏是这样的：

先把暴力两两对比方案说一遍，主动分析出复杂度问题，说明不可取；然后写出排序归一发，分析O(n k log k)；接着很自然地说一句"如果字符串特别长，可以用计数法把排序开销省掉"，再写出计数法。整个过程展示的是你思考问题的递进过程，而不是背题解。面试官看重的往往不是你第一遍就写出最优解，而是你能否在分析中自己发现问题并优化。

6. 这类题的通用解法模板：能一通百通的姊妹题

6.1 有效的字母异位词：判断两个字符串是否异位

LeetCode 第 242 题，输入两个字符串，判断它们是否互为字母异位词。这题是字母异位词分组的"降级版"，只需要判断一组而不是分组。

解法非常固定：长度不同直接返回 false；否则用一个长度为 26 的频次数组，遍历第一个字符串时+1，遍历第二个时-1，最后检查整个数组是否全是 0。时间复杂度O(k)，空间O(1)。

这题的陷阱在于，有人会用排序法sorted(s) == sorted(t)来解，但这样时间复杂度变成了O(k log k)，在线性时间能解决的问题没必要绕远路。把 242 题的思路吃透之后，再回头看 49 题，你就能更好地理解为什么计数法才是正主。

6.2 找到字符串中所有字母异位词的起始下标：滑动窗口

LeetCode 第 438 题，给你两个字符串s和p，要求在s中找到p的所有字母异位词子串，返回它们起始下标。

这题是异位词思想的进阶用法，核心是滑动窗口 + 频次数组。窗口长度固定为len(p)，每向右滑动一个字符，就把新字符加进窗口频次，把滑出窗口的字符移出频次，然后和p的频次数组比对。

暴力写法是在每个位置重新统计窗口内频次，复杂度O(n * k)会超时；优化方法是维护一个match变量记录两个频次数组中有多少个位置是匹配的，每次滑动只更新一两个位置，判断就能做到O(1)，总复杂度降到O(n)。如果你刚刷完 49 题，再来做 438 题会非常顺手，因为两者的核心理解都在"频次数组"这个统一模型上。

6.3 同构字符串、单词规律：双向映射思想

LeetCode 第 205 题（同构字符串）和第 290 题（单词规律），虽然挂着"哈希"的标签，但做题逻辑和 49 题又不太一样。这两题考的是一对一的双向映射：字符到字符，或字符到单词。

我之所以把这两道并列讲，是因为很多人在做 205 题时会犯同一个错误：只用一个dict记录s到t的映射，而不检查反向映射。比如s = "ab"，t = "aa"，单方向看a -> a、b -> a是合法的，但反过来a同时对应a和b，非法。解决办法是维护两个 dict 做双向校验。

这和 49 题看似不同，其实底层逻辑相通：都在强调映射关系必须唯一。49 题的 key 必须是"多对一"（多个异位词归到同一个 key），而 205 题要求"一对一"（一个字符不能映射成两个字符）。弄清楚映射方向，哈希类的题基本不会有太大偏差。

6.4 冷门但有趣的思路：质数乘积法

还有一个值得了解的冷门方案：给小写字母分别赋一个质数，a -> 2，b -> 3，c -> 5，以此类推，然后计算每个单词所有字母对应质数的乘积，作为 key。

根据算术基本定理，一组质数的乘积是唯一的，所以异位词的质数乘积必然相同。这个方案的理论复杂度是O(n * k)，但实际应用中乘积会膨胀得非常快，很快超出普通整形的表示范围。Python 的整型是任意精度的，所以能撑住，但 C++ 和 Java 就要用大数类，反而拖慢速度。

所以这个思路更适合当拓展知识来理解，不适合实战提交。知道它的存在就够了，面试如果提到哈希冲突相关的考点，你还能拿它举例子。

最后分享一点个人体会。

这道题我在不同阶段刷过至少四遍，每次都有新感悟。大一第一次见它，觉得哈希表好神奇；大四准备面试时做它，已经能熟练讲出排序法和计数法的复杂度差异；到了研一，我更关注的是它背后的抽象能力——所有"分组"问题，本质上都是为对象找一个合适的不变量。这种能力不只在刷题时有用，做工程时处理日志归类、做数据清洗时按特征聚类，底层思路都是一模一样的。

如果你刚开始刷题，我的建议是别急着直接看题解。先自己写一版暴力解，哪怕超时也没关系；再想一想"怎么提一个全局标识"，逼自己找出排序法；最后再思考有没有不排序的办法，能自己推导出计数法。这个过程远比我在这里讲一遍有价值。按这个节奏把 49 题吃透，你收获的绝对不只是这一道题的解法。