LeetCode LCR 032. 有效的字母异位词

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 032. 有效的字母异位词

题意分析

判断两个字符串 s 与 t 是否互为变位词。题目给出的定义有两个条件：每个字符出现的次数都相同，并且字符顺序不完全相同。第二个条件是本题与常见版本最大的区别——s 与 t 完全一样时要返回假，而不是真。

第一个条件说明「顺序无关，只关心每个字符出现多少次」。既然只在意计数，那么两个字符串是否互为变位词，等价于它们的字符频次向量是否完全相同。

由此立刻得到一个必要条件：长度不等一定不是变位词，因为频次向量的元素之和就是长度。这条可以作为最廉价的提前返回。

字符集约束是关键的算法信号：题目限定只含小写字母，也就是最多 26 种字符。这意味着「频次向量」是一个定长为 26 的整数数组，而不是需要动态扩容的映射结构——空间是常数而非 $O(n)$。

边界要覆盖：两串长度不同；两串完全相同（按定义返回假）；长度相同但字符集合完全不同；以及含重复字符时必须比较次数而非仅比较是否出现过。

解法：哈希表统计状态

核心思路

最容易想到的做法是把两个字符串各自排序后比较是否相等，正确但要 $O(n \log n)$ 时间，而且排序本身做了远超需求的事——我们只想知道每种字符有多少个，并不需要它们的相对次序。

瓶颈定位到这里，改进方向就清楚了：直接统计频次。开一个长度 26 的数组 cnt，cnt[c - 'a'] 表示字符 c 的净出现次数。

更进一步，不必统计两遍再逐位比较。因为两串长度相等，可以在同一次遍历里对 s 的字符做加一、对 t 的字符做减一。这样定义之后，不变量非常干净：遍历结束时 cnt[k] 等于字符 k 在 s 中的出现次数减去在 t 中的出现次数。

于是判定条件就是：cnt 全为 0 当且仅当两串的频次向量完全相同。任意一位非零都说明某个字符两边数量不匹配，直接返回假。

剩下的是题目特有的第二个条件。长度不等直接返回假（频次和不同）；s 与 t 内容完全相同也要返回假（顺序完全相同，不满足「顺序不完全相同」）。两者都是纯粹的字符串比较，合并成一个提前返回写在最前面即可，代价是 $O(n)$，不影响总复杂度。

注意这个提前返回不能省：如果只判长度不判相等，s = "ab"、t = "ab" 的 cnt 会全为 0，函数错误地返回真。

解题步骤

提前返回：if (m != n || s.equals(t)) return false;。长度不同意味着频次和不同，必然不是变位词；内容完全相同则违反「顺序不完全相同」这一条，这是本题特有的判定，漏掉会在 s == t 的用例上翻车。

开定长计数数组：int[] cnt = new int[26]。用定长数组而不是哈希映射，是因为字符集已被限定为 26 个小写字母，定长数组访问是一次寻址、没有哈希计算与装箱开销。

一次遍历同时加减：++cnt[s.charAt(i) - 'a']; --cnt[t.charAt(i) - 'a'];。因为已经确认两串等长，同一个下标 i 可以安全地同时索引两串，省掉一次循环。- 'a' 把字符映射到 [0, 25] 的下标。

检查是否全零：遍历 cnt，只要有一位非零就返回假。这里检查的是「等于 0」而不是「大于等于 0」，因为多一个和少一个都算不匹配。

返回真：全零说明两串频次完全一致，且已在开头排除了完全相同的情形。

以 s = "anagram"、t = "nagaram" 走一遍。两串长度都是 7，内容不同，通过提前返回。

逐位处理：i=0 时 a 加一、n 减一，cnt[a]=1、cnt[n]=-1；i=1 时 n 加一、a 减一，两者回到 cnt[a]=0、cnt[n]=0；i=2 时 a 加一、g 减一；i=3 时 g 加一、a 减一，又都归零；i=4 时 r 加一、r 减一，净变化为零；i=5 时 a 加一、a 减一；i=6 时 m 加一、m 减一。最终 cnt 全为 0，返回真。

再看 s = "rat"、t = "car"：长度相同且内容不同，进入统计。i=0：r 加一、c 减一；i=1：a 加一、a 减一（净零）；i=2：t 加一、r 减一。最终 cnt[r] = 1 - 1 = 0、cnt[c] = -1、cnt[t] = 1。扫描时遇到 cnt[c] = -1 非零，返回假。注意这里 r 那一位恰好抵消成 0，说明只看某一位不足以下结论，必须全部为零才行。

最后看本题特有的用例 s = "ab"、t = "ab"：长度相同但 s.equals(t) 为真，提前返回假。如果跳过这个判断直接统计，cnt 会全为 0 从而错误地返回真。

代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        int m = s.length();
        int n = t.length();
        // 长度不等必不匹配；完全相同则违反「顺序不完全相同」。
        if (m != n || s.equals(t)) {
            return false;
        }
        // 字符集固定 26 个小写字母，定长数组即可。
        int[] cnt = new int[26];
        for (int i = 0; i < m; ++i) {
            // cnt[k] 的含义：字符 k 在 s 中的次数减去在 t 中的次数。
            ++cnt[s.charAt(i) - 'a'];
            --cnt[t.charAt(i) - 'a'];
        }
        for (int x : cnt) {
            if (x != 0) {
                return false;
            }
        }
        return true;
    }
}

func isAnagram(s string, t string) bool {
    m, n := len(s), len(t)
    // 长度不等必不匹配；完全相同则违反「顺序不完全相同」。
    if m != n || s == t {
        return false
    }
    // 字符集固定 26 个小写字母，定长数组即可。
    cnt := [26]int{}
    for i, c := range s {
        // cnt[k] 的含义：字符 k 在 s 中的次数减去在 t 中的次数。
        cnt[c-'a']++
        cnt[t[i]-'a']--
    }
    for _, x := range cnt {
        if x != 0 {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$，n 为字符串长度。提前返回里的相等判断最多扫一遍，主循环恰好一遍，最后检查 cnt 是固定 26 次，三部分都是线性或常数，没有排序带来的对数因子。

空间复杂度：$O(1)$。计数数组长度恒为 26，由字符集大小决定而与输入长度无关；除此之外只有几个整型变量，没有开与 n 同阶的结构。

关键点总结

「顺序无关、只看组成」的判定一律转化为频次向量比较，这是异位词类问题的统一入口，比排序更快也更能表达意图。

「加一减一合并成一次遍历」让判定条件坍缩为「数组全零」，比维护两个数组再逐位比对更短，也少一次遍历。

字符集有限是使用定长数组而非哈希映射的依据，看到「仅含小写字母」这类约束就应该立刻把空间从 $O(n)$ 降到 $O(1)$。

本题定义里的「顺序不完全相同」是与常见版本的实质差异，读题时要逐句核对判定条件，不能凭对经典题的印象直接套模板。

长度相等是合并遍历的前提，先做长度检查既是剪枝也是后续同下标访问的安全保证。

面试视角：先给排序解法说明思路，再指出计数解法把时间降到 $O(n)$、空间降到 $O(1)$；如果面试官把字符集放宽到 Unicode，要能立刻改口——定长数组换成哈希映射，空间变成 $O(k)$，k 为不同字符数，并注意按码点而非按字节遍历。

易错点总结

漏掉 s.equals(t) 的判断：s = "ab"、t = "ab" 会因计数全零而返回真，但本题定义要求顺序不完全相同，正确答案是假。

漏掉长度判断直接同下标遍历：s = "ab"、t = "abc" 时按 s 的长度循环会漏掉 t 的最后一个字符，错误返回真；按 t 的长度循环则会越界。

只检查某一位是否为零就下结论：s = "rat"、t = "car" 中 r 那一位恰好抵消为 0，提前返回真会漏掉 c 与 t 的不匹配。

把判定写成 cnt[x] >= 0：s = "aabb"、t = "abbb" 中 a 那一位是正数、b 那一位是负数，只判非负会错误返回真。

用集合而不是计数：s = "aab"、t = "abb" 的字符集合都是 {a, b}，用集合比较会错误返回真，必须比较次数。

下标写成 s.charAt(i) 而不减 'a'：小写字母的码点是 97 起，直接当下标会越出长度 26 的数组，抛数组越界异常。

Go 里用 for i, c := range s 却把 i 当字符下标去索引含多字节字符的 t：本题限定小写字母所以安全，但一旦字符集放宽到中文或带重音字符，i 是字节偏移而非字符序号，取到的会是半个字符。

先排序再比较却修改了原字符串所依赖的顺序信息：排序解法本身正确，但会把「顺序不完全相同」这条信息抹掉，必须在排序之前先做 s.equals(t) 判断，否则同样会误判。

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	判定条件里没有「顺序不完全相同」，两串相同时应返回真
49. 字母异位词分组	中等	从两两判定升级为分组，需要把频次向量固化成可作哈希键的签名
383. 赎金信	简单	判的是包含而非相等，只要求每一位计数不小于零，长度可以不同
面试题 01.02. 判定是否互为字符重排	简单	与 242 同型，但字符集可能扩大到 ASCII，计数数组要开到 128
387. 字符串中的第一个唯一字符	简单	同样先计数，但要第二次遍历原串找出首个计数为 1 的位置
451. 根据字符出现频率排序	中等	计数之后还要按频次降序重建字符串，考察计数与排序的衔接
1002. 查找共用字符	简单	把两串比较推广到多串，对每一位取所有字符串计数的最小值
剑指 Offer 50. 第一个只出现一次的字符	简单	只需找唯一字符，返回的是字符本身而非下标，可用计数或有序映射