LeetCode 242简单哈希计数
有效的字母异位词 图解题解
两个字符串字母一模一样只是顺序不同？一张 26 格的账本，一次对消就能验出来。
想象你要核对两份采购清单是否完全一样。先按清单 s 逐项在账本里记上去（苹果+1、香蕉+1……）；再拿清单 t 逐项对消（苹果-1、香蕉-1……）。两张单走完，26 个格子全归零，说明完全一致；任何一格不是零，说明有差异。这道题的字母计数器，干的就是这件事。
这道题到底在问什么
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
- s
- "anagram"
- t
- "nagaram"
- 输出
- true
最优解：一步一步想明白
- 3核心做法：维护一张计数表 cnt。遍历 s 时每个字符 +1，遍历 t 时每个字符 -1。如果两个串字母完全一致，加进去的和减出来的会刚好抵消，所有计数都回到 0。
- 4先比长度，再准备空计数表 cnt输入 s = "anagram"，t = "nagaram"。先做最快的判断：长度不等就直接 false。这里两者长度都是 7，可以继续。下方数组展示的是 s 的字符，右侧计数表 cnt 现在是空的。
- 5指向 s[0] = 'a'，准备 +1遍历 s 的第 0 个字符 'a'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 6cnt['a'] += 1 → 1在计数表里给 'a' 加一，它现在的计数是 1。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 7指向 s[1] = 'n'，准备 +1遍历 s 的第 1 个字符 'n'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 8cnt['n'] += 1 → 1在计数表里给 'n' 加一，它现在的计数是 1。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 9指向 s[2] = 'a'，准备 +1遍历 s 的第 2 个字符 'a'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 10cnt['a'] += 1 → 2在计数表里给 'a' 加一，它现在的计数是 2。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 11指向 s[3] = 'g'，准备 +1遍历 s 的第 3 个字符 'g'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 12cnt['g'] += 1 → 1在计数表里给 'g' 加一，它现在的计数是 1。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 13指向 s[4] = 'r'，准备 +1遍历 s 的第 4 个字符 'r'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 14cnt['r'] += 1 → 1在计数表里给 'r' 加一，它现在的计数是 1。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 15指向 s[5] = 'a'，准备 +1遍历 s 的第 5 个字符 'a'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 16cnt['a'] += 1 → 3在计数表里给 'a' 加一，它现在的计数是 3。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 17指向 s[6] = 'm'，准备 +1遍历 s 的第 6 个字符 'm'（橙色）。先看清是哪个字符，下一步把它加进计数表。
- 18cnt['m'] += 1 → 1在计数表里给 'm' 加一，它现在的计数是 1。s 走完后，cnt 记录的就是 s 里每个字母各出现了几次。
- 19s 全部 +1 完毕，得到 s 的字母频次s 遍历结束，计数表记下了 s 里每个字母的个数：a×3、n×1、g×1、r×1、m×1。下一阶段拿 t 的每个字符来抵消，把计数一个个减回去。
- 20cnt['n'] -= 1 → 0遍历 t 的第 0 个字符 'n'（黄色高亮）。在计数表里给 'n' 减一，它现在的计数是 0。s 加的、t 减的正好对应，计数在一步步归零。
- 21cnt['a'] -= 1 → 2遍历 t 的第 1 个字符 'a'（黄色高亮）。在计数表里给 'a' 减一，它现在的计数是 2。s 加的、t 减的正好对应，计数在一步步归零。
- 22cnt['g'] -= 1 → 0遍历 t 的第 2 个字符 'g'（黄色高亮）。在计数表里给 'g' 减一，它现在的计数是 0。s 加的、t 减的正好对应，计数在一步步归零。
- 23cnt['a'] -= 1 → 1遍历 t 的第 3 个字符 'a'（黄色高亮）。在计数表里给 'a' 减一，它现在的计数是 1。s 加的、t 减的正好对应，计数在一步步归零。
- 24cnt['r'] -= 1 → 0遍历 t 的第 4 个字符 'r'（黄色高亮）。在计数表里给 'r' 减一，它现在的计数是 0。s 加的、t 减的正好对应，计数在一步步归零。
- 25cnt['a'] -= 1 → 0遍历 t 的第 5 个字符 'a'（黄色高亮）。在计数表里给 'a' 减一，它现在的计数是 0。s 加的、t 减的正好对应，计数在一步步归零。
- 26cnt['m'] -= 1 → 0遍历 t 的第 6 个字符 'm'（黄色高亮）。在计数表里给 'm' 减一，它现在的计数是 0。s 加的、t 减的正好对应，计数在一步步归零。
- 27所有计数都归零 → 完全匹配t 遍历结束，回头看计数表：a=0、n=0、g=0、r=0、m=0，全部归零。这说明 s 加进去的和 t 减出来的字母完全一致，t 确实是 s 的异位词。
- 28return true计数表全为 0，返回 true（绿色标出完全匹配的 s）。整个过程把 s、t 各扫一遍，只用一张大小固定（最多 26 个字母）的计数表。
- 31记住这题的骨架：用一张计数表，s 加 t 减，靠「最后全为 0」来判断两个串字母种类和个数是否完全一致。
⚠️ 容易写错的地方
✗ 错：不先比长度
✓ 对：长度不等直接 false
长度都不一样，字母个数不可能全相同，先挡一刀更快
✗ 错：两次完整排序再比较
✓ 对：一张计数表 s 加 t 减
排序是 O(n log n)，计数是 O(n)，更快
✗ 错：t 减完才检查负数
✓ 对：减的当下就判 < 0
一旦某字符计数为负就能立刻返回，不必等全部减完
完整代码（Python / C++ / Java）
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord("a")] += 1
for ch in t:
cnt[ord(ch) - ord("a")] -= 1
if cnt[ord(ch) - ord("a")] < 0:
return False
return TrueC++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int cnt[26] = {0};
for (char ch : s) cnt[ch - 'a']++;
for (char ch : t) {
if (--cnt[ch - 'a'] < 0) return false;
}
return true;
}
};Java
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] cnt = new int[26];
for (char ch : s.toCharArray()) cnt[ch - 'a']++;
for (char ch : t.toCharArray()) {
if (--cnt[ch - 'a'] < 0) return false;
}
return true;
}
}复杂度
时间复杂度
O(n)
s、t 各扫一遍
空间复杂度
O(1)
计数表固定 26 个字母
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 有效的字母异位词 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「哈希计数」，换最直接的暴力解会差在哪？+
哈希计数抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 有效的字母异位词 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。