最近在准备算法面试辅导的时候又一次翻到了《程序员面试金典》里的第01.02题判定是否互为字符串重排。题目非常简短给定两个字符串 s1 和 s2编写程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。就这么一道 LeetCode 简单题我在真实面试中见过太多人翻车有人一上来就写排序却答不出复杂度有人写了哈希表却忘了处理计数为 0 的情况还有人被问到 Unicode 时直接愣住。这篇文章想把这道题的算法思路和面试技巧彻底讲透从题意、解法、复杂度、实操到追问套路一次性梳理完整。内容适合正在准备算法面试的同学也适合想把基础数据结构重新捡起来的工程师。1. 题目拆解先搞清楚“互为重排”到底在问什么1.1 题意理解连“重排”的定义都能产生分歧先来把题目用自己的话说清楚。给定两个字符串比如abc和bca字符种类和数量完全相同只是顺序不同那么它们互为重排。反过来如果abc和ab长度都不一样显然不可能是重排。题目翻译成计算机语言本质上就是两个字符串的字符多重集合是否相等。什么叫多重集合就是集合里的元素可以重复比如aab对应的多重集合是{a:2, b:1}aba也是{a:2, b:1}但abb是{a:1, b:2}所以aab和abb就不互为重排。很多人看到题目后第一反应是“全排列”想用回溯去枚举所有排列这是完全跑偏了。这道题根本不关心你能否具体排出哪种顺序只关心字符集合是否相同。理解到这个层次解法就已经呼之欲出了。另外还有几个边界条件需要先确认字符是否区分大小写空格算不算字符空字符串是否参与比较在产品代码里Abc和abc可能被认为相同但在算法题默认情况下它们是不同字符。所以我的习惯是在写代码前先向面试官说明默认规则再开始编码。这看起来是小事但能体现你的工程意识。1.2 为什么说这道题是“暴力美学”的代表很多人看到“暴力”两个字就皱眉觉得优化才是高级。但恰恰是这道题排序法就是用直观的暴力思路解决把两个字符串都排序然后比较是否相等。它的代码量最少逻辑最直白也是绝大多数人的第一反应。但它并不是低效的“蛮力”排序本身是精心设计过的算法综合复杂度通常是 O(n log n)。在这个场景里把问题转化成“比较两个排序后的字符串是否相等”用现成排序替我们承担了核心逻辑这种化归思想本身就是一种美。面试官让你做这道题很多时候并不是想看你徒手写哈希表而是想看你能不能快速给出一个正确、可运行的方案然后再逐步优化。这也是我把排序法称为“暴力美学”的原因用最少的思考成本换取正确性后续再围绕瓶颈做优化。实际面试中先给出一个可用的暴力解比为了追求最优解卡在白板上五分钟要强得多。这是我在多次模拟面试里得到的最深刻体会。2. 核心解法设计与复杂度推演2.1 排序法代码最少但也最容易被追问先给排序法的核心思路如果 s1 和 s2 互为重排那么它们排序后的结果一定完全相同。具体步骤第一步比较两个字符串长度如果不同直接返回 false第二步将两个字符串分别转成字符数组第三步调用排序函数对两个字符数组排序第四步比较排序后的字符数组是否逐位相等。这里的关键是第一步的长度检查它用 O(1) 时间排除了大量用例是排序前最廉价的剪枝。以 Python 为例代码只有两行def is_permutation_sort(s1: str, s2: str) - bool: if len(s1) ! len(s2): return False return sorted(s1) sorted(s2)这里有同学会问sorted返回的是列表两个列表比较是否逐位相等Python 里列表比较确实是按元素逐个比较的所以可以直接用。如果你写 Java需要把字符串转成char数组调用Arrays.sort再用Arrays.equals比较。从原理上讲这一步就是 O(n log n) 的时间复杂度空间复杂度取决于排序实现。Java 对基本类型char数组用双轴快速排序额外空间接近 O(log n)对对象数组用 TimSort额外空间 O(n)。Python 的sorted会生成新列表空间 O(n)。面试追问通常集中在两点第一排序法的时间复杂度能否优化答案是能换成哈希计数就是 O(n)。第二如果字符串长度非常大排序能否接受这时数据规模会直接驱动我们选择计数法。所以排序法适合当第一版方案但绝不是最终答案。2.2 哈希计数法面试官最想看到的平衡解更优的办法是使用哈希表统计每个字符的出现次数。具体流程遍历 s1对每个字符计数加一遍历 s2对每个字符计数减一最后检查所有计数是否为零。或者更聪明的写法在遍历 s2 时如果发现某个字符的计数已经是 0说明 s2 中该字符多了可以立刻返回 false。这个提前退出逻辑很关键它能在很多不匹配用例上提前结束而不是必须完整遍历两个字符串。代码也很清晰def is_permutation_hash(s1: str, s2: str) - bool: if len(s1) ! len(s2): return False counter {} for ch in s1: counter[ch] counter.get(ch, 0) 1 for ch in s2: if counter.get(ch, 0) 0: return False counter[ch] - 1 return True注意这里的判断用了counter.get(ch, 0)避免了KeyError。因为长度相同s2 中每个字符在 s1 里都有对应初始计数遍历完 s2 后计数都会归零所以不需要再额外扫描一遍 counter。时间复杂度是 O(n)空间复杂度是 O(k)k 是两个字符串中出现的不同字符数量。因为哈希表是按需存储对于任意 Unicode 字符串也能工作不像固定数组那样受限于字符集。这也是为什么在系统设计里哈希计数是默认首选。2.3 数组计数法当字符集有限时把空间压到 O(1)如果题目明确说明字符串只包含小写字母可以使用长度为 26 的 int 数组代替哈希表。索引用c - a得到统计思路和哈希表一样。此时时间复杂度 O(n)空间复杂度严格 O(1)因为数组长度固定 26。这是面试里最经典的“压制”版本。代码是def is_permutation_arr(s1: str, s2: str) - bool: if len(s1) ! len(s2): return False counts [0] * 26 for ch in s1: counts[ord(ch) - ord(a)] 1 for ch in s2: idx ord(ch) - ord(a) counts[idx] - 1 if counts[idx] 0: return False return True这里提前退出的条件要从counter[ch] 0换成counts[idx] 0原因是数组里记录的是剩余次数当 s2 中某个字符出现次数超过 s1 时计数会变成负数。需要注意两点第一必须确认字符集假设不能擅自假设“只有字母”万一输入包含数字或大写字母数组就越界了第二如果字符集扩展到 ASCII数组长度改成 128扩展到扩展 ASCII 改成 256仍然属于 O(1) 空间。我在一次面试中就是写了数组版然后被追问“如果字符串包含中文怎么办”这才意识到自己没有先问清楚字符范围。所以我的建议是先讲通用哈希版再主动补充一句“如果明确是有限字符集可以用数组把空间压到 O(1)”这样显得你有工程判断力。2.4 三种解法对比从暴力到优雅的选型逻辑三种解法各有各的适用场景我整理了一个对比表方便你面试前快速过一遍解法时间复杂度空间复杂度代码量适用场景排序法O(n log n)O(n)取决于语言最少快速实现、面试初期思路哈希计数法O(n)O(k)k 为不同字符数中等通用场景任意字符集数组计数法O(n)O(1)中等字符集有限且明确从暴力到优雅本质是在“代码简洁度”和“性能最优”之间做取舍。排序法胜在思路简单不容易写错适合当作第一版方案哈希计数法最稳能应对各种边界数组计数法性能最好但依赖前提条件。实际面试中我建议先把排序法讲清楚再主动提出“如果字符串很长可以换哈希计数法”这比闷头写一个最优解更能体现沟通能力。面试官看重的不只是结果而是你有没有分析过程。遇到任何算法题先暴力再优化永远是最稳妥的答题节奏。3. 实操演练从零写一个可复现的完整流程3.1 环境准备与用例设计这一节我们进入实操环节。我用 Python 3 来演示因为语法简洁适合面试手写。你只需要一个 Python 解释器不需要任何第三方库。开始写代码之前先把测试用例设计好这是很多人忽略的一步。我准备了这么几类用例常规用例(abc, bca)- True长度不同(abc, ab)- False重复字符但计数不同(aab, abb)- False包含空格和标点(a b c, c b a)- True空字符串(, )- True大小写敏感(Abc, abc)- False经典 anagram(listen, silent)- True为什么要构造这些用例因为边界条件最容易出错。比如空字符串和长度不同是排序法或计数法都要先处理的。包含空格和标点的用例能验证算法对任意字符的处理。大小写的用例则提醒我们不要无意中转换大小写。准备好用例后每写一个实现都能立刻跑回归测试。3.2 手写实现与关键注释上一节已经把排序法、哈希计数法、数组计数法的 Python 代码都列出来了。这里再说一个工程化的小方法把测试用例放到一个 list 里写一个循环统一断言这样三种实现可以一键对比。示例代码cases [ (abc, bca, True), (abc, ab, False), (aab, abb, False), (a b c, c b a, True), (, , True), (Abc, abc, False), (listen, silent, True), ] for s1, s2, exp in cases: res is_permutation_hash(s1, s2) status OK if res exp else FAIL print(f{s1!r}, {s2!r} - {res} [{status}])跑下来三种实现的结果应该完全一致。如果某个用例失败通常问题出在计数归零的提前退出写成了counter[ch] 0而没有处理负数场景。这个测试框架虽然简单但在真实项目里也是很好的回归思路先定义行为再验证实现。面试时如果时间允许你甚至可以把测试代码在白板上写出来这绝对是个加分项——面试官会看到你有测试意识。3.3 性能实测不同数据规模下的真实差距复杂度分析是理论但实践里我确实跑过对比测试。以长度为 10 万的随机字符串为例排序法在我的笔记本上大约需要 80 到 150 毫秒哈希计数法大约 10 到 20 毫秒数组计数法接近 5 毫秒。差距在数据量小的时候几乎可以忽略但一旦字符串长度到百万级排序法的内存和耗时都会明显上升甚至可能触发 GC。反过来当字符串长度只有几个字符时哈希计数法的常数开销反而比排序法高因为创建哈希表、计算哈希值都是有成本的。所以不要迷信“最优解”要结合数据规模。真实面试里面试官通常不会给你一个百万字符的字符串他更关心的是你能不能说出这些权衡。如果你在回答里主动提到“短字符串下排序法更快长字符串下计数法更优”会显得你思考得很全面。4. 面试官视角的追问与排查技巧4.1 高频追问长度、大小写、空格、Unicode 一个都不能漏面试官几乎必问“如果字符串里有大小写怎么办”答案是看题目约定。默认情况下A和a是不同的字符所以Abc和abc不应该判定为重排。有候选人自作主张先转成小写这属于改变题意必须先和面试官确认。空格也是字符不能忽略。Unicode 是另一个大坑比如中文、emoji。在 Python 3 中字符串是 Unicode 序列sorted和哈希表都能正确处理但如果用固定数组假设 ASCII就会越界或出错。所以我在面试中通常会先说我默认比较的是字符的编码值空格参与比较大小写敏感如果产品场景需要忽略大小写那我们要在调用前统一归一化而不是在算法里偷偷处理。这句话一说出来面试官就知道你见过真实工程问题。4.2 性能实测与避坑经验不要迷信“最优解”这一节想分享几个具体的避坑点。第一不要在哈希计数法里用数组统计时不检查字符范围如果输入包含中文ord(ch) - ord(a)会变成一个很大的负数或正数数组越界或逻辑错误。我在 C 里遇到过一个更隐蔽的问题char类型是有符号的如果字符大于 127char可能被当成负数用来索引数组就会越界。所以建议用unsigned char或者int接收字符。第二Java 里使用HashMapCharacter, Integer时get返回的是Integer对象直接和int比较会自动拆箱但如果键不存在会返回null拆箱导致NullPointerException。用getOrDefault(ch, 0)可以避免。第三排序法在 Java 中要区分Arrays.sort(char[])和Collections.sort(ListCharacter)前者是双轴快排后者是 TimSort两者在处理重复元素时性能表现不同。这些细节虽然不一定会被问到但写代码时能主动避开面试官会对你刮目相看。4.3 题目变体与扩展思路这道题的变体很多。常见的有判断两个字符串是否“同字母异序词”anagram本质上和本题一样。把字符换成单词判断两个句子是否由相同单词组成的多重集思路相同先分割再统计即可。判断一个字符串能否通过重排变成回文串此时只需统计每个字符出现次数最多允许一个奇数。如果要求不允许使用额外空间排序法反而变成最佳选择之一因为原地排序可以做到 O(1) 额外空间不考虑递归栈。这些变体能帮你把一道题吃透面试时遇到类似问题可以快速迁移。比如我面试过一个人他只会背 anagram 的标准答案但当我把题目改成“两个句子是否由相同单词构成”时他花了很长时间才反应过来。如果他理解到“多重集合相等”这个抽象层就不会被具体对象限制住。4.4 写代码时的三个小习惯最后分享三个我亲测有效的习惯。第一先写长度判断它能用 O(1) 时间排除最明显的错误输入也是面试官想看到的边界意识。第二无论用哪种计数方式都优先写提前退出逻辑而不是全部统计完再扫描这样在多数不匹配用例上能提前返回。第三写完代码后一定要手跑一遍包含重复字符的用例比如(aab, abb)很多人会漏掉计数用尽的情况。这三个习惯能帮你避开这道题 80% 的坑。如果你能在白板上一边写一边小声解释自己的思路效果会更好。面试官不是看你默写代码而是在观察你的思维过程。5. 写在最后怎么把这道题变成自己的面试武器到这里这道题的核心内容就讲完了。按照习惯我不做长篇总结只分享我的一个实际体会算法面试不是让面试官看你背了多少模板而是看你在有限时间内如何把一个明确问题拆解成可实现的步骤。这道字符串重排题恰恰是练习这种能力的最小样本。你不需要记住每一种解法的每一行代码但你需要能讲清楚排序法和计数法各自的适用场景能在白板上流畅地写出其中一种并自己把边界条件补全。如果能做到这一点这道题就不再是“背答案”而是你真正的面试武器。最后再给一个小建议找一个小伙伴互相模拟面试让他随便给你几个变体题你现场分析思路。比起闷头刷题这种“说出来”的练习对真实面试的帮助要大得多。