30 seconds of code:用 JavaScript 判断两个字符串是否互为 Anagram
30 seconds of code:用 JavaScript 判断两个字符串是否互为 Anagram
导读
在字符串处理与算法面试中,anagram(易位构词)判断是一道高频基础题:两个字符串包含相同的字符、只是顺序不同,即为互为 anagram。本篇文章以 30 seconds of code 仓库中的 is-anagram 代码片段 为核心,系统讲解"先归一化、再排序比较"的经典解法,并结合同仓库的字符串工具函数与排列生成示例,为你提供可直接复制、可验证、可扩展的完整实战方案。读完本文,你将掌握正则表达式清理、大小写统一、字符排序等组合技巧,并能独立写出健壮、可读的 isAnagram 实现。
Anagram 的定义与判断思路
Anagram 的数学定义很清晰:一个字符串是另一个字符串的 anagram,当且仅当二者包含 完全相同的字符集合(含重复次数),只是排列顺序不同。
在真实场景中,判断两个字符串是否互为 anagram 时,我们通常还要忽略大小写、空格、标点符号和特殊字符。例如:
"iceman"与"cinema":互为 anagram(true);"Listen"与"Silent":忽略大小写后互为 anagram(true);"rail safety"与"fairy tales":去掉空格后互为 anagram(true);"hello"与"hallo":仅一个字符不同,不是 anagram(false)。
针对这个定义,最直观、最简单的比较策略是 归一化(normalize):先把两个字符串统一成"干净、有序"的标准形态,然后直接比较两个归一化结果是否相等。只要归一化规则一致,任何一对原始字符串都能通过"标准化 + 等值比较"得到正确答案。
基于 30 seconds of code 的标准实现
is-anagram 代码片段 给出的实现正是"归一化 + 排序 + 比较"这一思路的直接落地:
const isAnagram = (str1, str2) => {
const normalize = str =>
str
.toLowerCase()
.replace(/[^a-z0-9]/gi, '')
.split('')
.sort()
.join('');
return normalize(str1) === normalize(str2);
};
isAnagram('iceman', 'cinema'); // true
这段代码的巧妙之处在于,把归一化逻辑封装成一个独立的 normalize 内部函数,主函数只负责"两个归一化结果是否相等"这一条比较逻辑,职责单一、可读性极强。
逐行拆解归一化管线
normalize 内部是一条标准的 字符串处理链式调用(method chaining),共分四步:
| 步骤 | 方法调用 | 作用 | 处理示例("Listen!") |
|---|---|---|---|
| 1 | toLowerCase() |
统一为小写,实现大小写不敏感 | "listen!" |
| 2 | replace(/[^a-z0-9]/gi, '') |
用正则删除所有非字母、非数字字符 | "listen" |
| 3 | split('') |
把字符串拆成单个字符的数组 | ["l","i","s","t","e","n"] |
| 4 | sort() + join('') |
按字符编码排序并重新拼接为字符串 | "eilnst" |
toLowerCase()保证了"Listen"与"silent"这类大小写差异不会影响判断;- 正则
/[^a-z0-9]/gi中,[^a-z0-9]匹配"不属于 a-z 小写字母和 0-9 数字"的任意字符,g标志(global)使其匹配全部而非首个,i标志(ignore case)让字符类也覆盖 A-Z 大写字母,配合toLowerCase()` 双保险地清除了空格、标点与特殊字符; split('')将字符串转为数组,Array.prototype.sort()默认按 Unicode 码点升序排列字符,join('')再把有序数组拼回字符串,从而得到"字符构成唯一"的标准化形态。
算法复杂度分析
从实现细节可以推导出该方案的时间与空间开销:
- 时间复杂度为 O(n log n),其中 n 是输入字符串的长度——瓶颈在于
sort()对字符数组的排序; - 空间复杂度为 O(n),
split('')产生的字符数组、排序过程中的临时存储都需要与字符串长度线性相关的内存。
因此,这一实现以"简单直白"取胜,适合绝大多数日常场景;只有当输入是超长字符串且对性能有苛刻要求时,才需要考虑下文介绍的计数器方案(以 O(n) 时间、O(1) 空间换取更高的效率)。
从源码看同类字符串工具:横向对照与深化
在 30 seconds of code 的 JavaScript 片段库中,"归一化字符串"是一类反复出现的通用模式,isAnagram 并非孤例。横向阅读这些片段,有助于你理解不同场景下归一化策略的取舍:
- compare-string-case-accent-insensitive 片段:用
Intl.Collator.prototype.compare()实现大小写与重音不敏感的比较。注意它与isAnagram的定位差异——Intl.Collator解决的是排序与比较的语义正确性,而isAnagram用toLowerCase()+ 正则实现的是字符集合等价性判断;如果你的 anagram 场景需要忽略é与e之类的重音差异,可参考该片段将normalize升级为str.normalize('NFD').replace(/[\u0300-\u036f]/g, '')后再清洗; - memoization 片段:其示例用递归回溯生成一个字符串的全部 anagram 排列(
anagrams('javascript')),与本文的"判断"互为补充——一个负责枚举所有排列,一个负责判定两串是否同构。若需实现"找出某字符串的所有 anagram 伙伴",可将二者组合使用; - normalize-line-endings 片段:展示了
replace(/\r?\n/g, normalized)的换行归一化思路,说明"先用正则清洗、再统一格式"是仓库中贯穿始终的字符串处理范式。
边界情况与扩展实战
不区分大小写、忽略标点的完整示例
把仓库片段的规则应用到常见输入上:
isAnagram('iceman', 'cinema'); // true
isAnagram('Listen', 'Silent'); // true
isAnagram('rail safety', 'fairy tales'); // true
isAnagram('A gentleman', 'Elegant man'); // true
isAnagram('hello', 'hallo'); // false
isAnagram('abc', 'abcd'); // false(长度不同)
isAnagram('', ''); // true(两个空串互为 anagram)
从上面最后一个例子可以看出,空串也会被正常处理:两个空串归一化后都是空串,结果为 true,这与"空串字符集合相同"的定义一致。
进阶 1:字符计数器方案(线性时间)
当需要更高性能或更严格的边界控制时,可以用字符计数替代排序。字符计数 + 长度预检的实现如下,它保持大小写不敏感,并在长度不等时提前返回 false:
const isAnagram = (str1, str2) => {
const clean = str => str.toLowerCase().replace(/[^a-z0-9]/gi, '');
const s1 = clean(str1);
const s2 = clean(str2);
if (s1.length !== s2.length) return false;
const count = new Map();
for (const ch of s1) count.set(ch, (count.get(ch) || 0) + 1);
for (const ch of s2) {
const remaining = (count.get(ch) || 0) - 1;
if (remaining < 0) return false;
count.set(ch, remaining);
}
return true;
};
该方案时间复杂度 O(n)、空间复杂度 O(1)(字符集有限),但代码明显更长。优先选择哪种,取决于你的场景:面试与教学推荐仓库的排序法(简洁直观),追求吞吐量时再改用计数器法。
进阶 2:支持重音字符的归一化
若业务数据包含 é、ñ 等重音字符,且希望 "cafe" 与 "café" 被视为等价,可先用 String.prototype.normalize('NFD') 将组合字符拆分为基础字符与附加符号,再删掉音标符号:
const normalize = str =>
str
.normalize('NFD')
.replace(/[\u0300-\u036f]/g, '')
.toLowerCase()
.replace(/[^a-z0-9]/gi, '')
.split('')
.sort()
.join('');
这一写法与仓库 remove-accents 片段 的剥离思路一脉相承,可视为对 isAnagram 的国际化增强。
总结
判断两个字符串是否互为 anagram 的核心方法论只有一句话:统一归一化规则,再比较标准化结果。30 seconds of code 的 is-anagram 片段 用 toLowerCase()、replace() 正则清洗、split()、sort()、join() 五步链式调用优雅地实现了这一思路,复杂度为 O(n log n),代码可读、可直接复用。在此基础上,你可以按需扩展为 O(n) 的计数器方案、支持重音字符的 Unicode 归一化方案,或者与仓库中生成全部 anagram 排列的递归工具组合使用,覆盖从算法练习到生产过滤的各类真实需求。