如何判断两个字符串是否为字母异位词？（LeetCode 242）

简化版

判断字符串 t 是否是 s 的字母异位词（anagram）——即两者包含完全相同的字母且每种字母出现次数也相同，只是排列不同（如 "anagram" 和 "nagaram"）。最优做法用计数：统计 s 中每个字母的出现次数，再用 t 去抵消，若最终计数全为 0 则是异位词。长度不等直接返回 false。若只含小写字母，用长度 26 的数组计数，O(n) 时间、O(1) 空间。

详细版

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;   // 长度不同直接排除
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;               // s 的字母 +1
        count[t.charAt(i) - 'a']--;               // t 的字母 -1
    }
    for (int c : count) {
        if (c != 0) return false;                 // 有字母没配平 → 不是异位词
    }
    return true;
}

核心：异位词 ⇔ 每种字母出现次数完全相同。
一趟计数抵消：s 的字母 ++、t 的字母 --，最后数组全 0 即是。
长度剪枝：长度不等必然不是异位词，先判省事。
复杂度：O(n) 时间；小写字母 O(1) 空间（26 数组）。

完整版教学

一、异位词的定义

字母异位词：两个字符串由相同的字母、相同的数量组成，只是顺序不同。所以判断的本质是比较两个字符串的「字母频次分布」是否一致——和字母的排列顺序无关，只和「每个字母各出现几次」有关。抓住这一点，解法自然浮现：统计并比较字母频次。

二、解法一：排序比较（简单但慢）

最朴素：把两个字符串各自排序，若排序后相等就是异位词（"anagram" 和 "nagaram" 排序后都是 "aaagmnr"）。

char[] a = s.toCharArray(); char[] b = t.toCharArray();
Arrays.sort(a); Arrays.sort(b);
return Arrays.equals(a, b);

优点是代码短、通用（不限字符集）；缺点是 O(n log n) 排序开销，不如计数快。

三、解法二：计数抵消（推荐，O(n)）

更优的是计数：用一个数组统计每个字母的净出现次数。遍历时 s 的字母 +1、t 的字母 -1，如果两者是异位词，每种字母的 +1 和 -1 恰好抵消，最终数组全为 0；只要有一个非 0，就说明某字母在两串中数量不同，不是异位词。

只需一趟遍历（同时处理 s 和 t 的同一下标，因为已判长度相等），再扫一遍 26 长度的数组检查是否全 0。O(n) 时间、O(1) 空间（26 固定）。

四、长度剪枝与字符集

长度不等直接 false：异位词必然等长，先判 s.length() != t.length() 能快速排除，也保证「一趟同下标遍历」不越界。
只含小写字母：用 int[26]，c - 'a' 做下标。
含大小写/Unicode：改用 HashMap<Character, Integer> 计数（或按需扩大数组）。面试常追问「如果是 Unicode 怎么办」——答哈希表，空间 O(字符种类数)。

五、相关变体

字母异位词分组（49）：把一堆字符串按「是否互为异位词」分组。做法是给每个字符串算一个规范化 key（排序后的字符串，或 26 长度计数拼成的字符串），key 相同的归一组。
找到字符串中所有字母异位词（438）：在长串里找所有「和短串互为异位词」的子串起点，用滑动窗口 + 计数，是本题的进阶。
有效的字母异位词但含空格/大小写：按题意预处理（转小写、去空格）再计数。

六、计数数组表达的是频次差

先对 s 的字符加一、再对 t 的字符减一后，计数数组保存 freq_s(c)-freq_t(c)。若长度相等且最终所有差值为 0，两串对每个字符的出现次数完全一致；反过来只要某个差值非零，就不可能通过重排得到另一串。

s="anagram", t="nagaram"
a: 3-3=0
n: 1-1=0
g: 1-1=0
r: 1-1=0
m: 1-1=0，其余也为 0
所以是异位词
而 "rat" 与 "car" 在 c/t 等位置差值非零

校验维度	本题必须保持的结论
循环/递推不变量	处理相同数量前缀时，每个桶等于 s 已读次数减 t 已读次数。
边界条件	26 长度数组只适用于明确的小写英文字母；Unicode 应按码点用 Map 计数。
复杂度与代价	计数法 O(m+n) 时间；固定字符集空间 O(1)，一般字符集空间 O(k)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：处理相同数量前缀时，每个桶等于 s 已读次数减 t 已读次数。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“s=“anagram”, t=“nagaram””开始手推，最后应得到“而 “rat” 与 “car” 在 c/t 等位置差值非零”。
边界复核：26 长度数组只适用于明确的小写英文字母；Unicode 应按码点用 Map 计数。
代价复核：计数法 O(m+n) 时间；固定字符集空间 O(1)，一般字符集空间 O(k)。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“处理相同数量前缀时，每个桶等于 s 已读次数减 t 已读次数。”这条正确性主线不能省。

八、常见误区与追问

误区：两个字符串包含相同字符种类就够了。 异位词还要求每种字符频次相同。
误区：排序法是 O(n)。 通用比较排序通常为 O(n log n)，计数法才是线性。
误区：Java 的 26 桶能正确处理所有字符。 非 a..z 字符会越界或碰撞，必须依据题目字符集选结构。
追问：为什么先判断长度？ 总字符数不同必不可能频次完全相同，也能避免后续无效扫描。
追问：能否在减计数时提前返回？ 若先完整统计 s，减 t 时某桶变负即可判 false，表示 t 某字符过多。
追问：分组异位词如何复用？ 把排序后字符串或规范化频次数组作为哈希键，将同键字符串归组。

九、加强记忆

判断字母异位词 = 比较两串的字母频次是否完全相同。计数法（推荐 O(n)）：先判长度不等则 false；一趟遍历 s 字母 +1、t 字母 -1，最后 26 长度计数数组全为 0 即是异位词。排序法（O(n log n)）：两串排序后相等即是，通用但慢。小写字母用 int[26]、O(1) 空间；Unicode 用 HashMap。进阶：异位词分组用「排序后的串」当 key，找所有异位词子串用滑动窗口。核心：顺序无关，只看每个字母各几个。

简化版

详细版