LeetCode 242. 有效的字母异位词

◎

本节目标

用固定大小的计数数组比较两个小写字符串的字符多重集合。

这道题对应字符串基础解题框架中的计数数组模型。两个字符串是否互为异位词，不取决于字符原来的位置，而取决于每个小写字母出现了多少次。

查看原题

朴素思路及瓶颈

朴素做法会对 s 的每个字符在 t 中搜索并删除一次，搜索和删除都可能线性，最坏为 O(n²)。排序后比较能降为 O(n log n)，但固定的 26 个小写字母已经给出了更小的状态空间。

净频次不变量

长度不同必然不是异位词。随后对 s 的字符加一、对 t 的字符减一；数组第 i 项始终表示字母 a + i 尚未抵消的次数。全部归零时，两串的字符多重集合相同。

代码实现

两种实现都只维护长度为 26 的整数数组，严格面向题目的小写英文字母约束；不会把字符排序，也不会建立不必要的映射。

C++

C++17

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }

        vector<int> counts(26);
        for (char ch : s) {
            counts[ch - 'a']++;
        }
        for (char ch : t) {
            counts[ch - 'a']--;
        }
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
};

Python

Python 3

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        for ch in t:
            counts[ord(ch) - ord('a')] -= 1
        return all(count == 0 for count in counts)

复杂度分析

• 时间复杂度：O(n + 26)，通常写作 O(n)。
• 空间复杂度：O(26)，即 O(1)。

易错点

• 忘记先比较长度，虽然最终也能发现不平衡，但没有利用最直接的失败条件。
• 将题目的小写约束扩展为任意字符，却仍使用 26 位数组。
• 只记录一串的出现次数而没有抵消另一串，无法判断多重集合相等。

模式迁移

当需要判断窗口内字符是否满足目标频次时，净频次可迁移为滑动窗口计数；当字母表不固定时，再把数组替换为哈希映射。异位词分组则把频次向量变成分组键。