0242. Valid Anagram

题目信息

题号:

0242

难度:

Easy

主题:

字符串、字符频次、哈希表、排序

原题:

LeetCode 0242

重点:

使用全部字符、每种字符频次完全相同、长度一致、小写英文字母

题目重述

给定两个字符串 s 和 t,判断 t 是否是 s 的字母异位词。字母异位词只能重新排列字符顺序,必须恰好使用 s 中的全部字符,因此两个字符串的长度以及每种字符的出现次数都必须完全相同。

s 和 t 的长度均位于 [1, 5 * 10^4],只包含小写英文字母。字符相同但频次不同、频次相同但存在不同字符,或者字符串长度不同,都应返回 false。函数不修改输入字符串。题目的进阶问题询问当输入包含 Unicode 字符时如何调整实现。

自建示例

重复字符频次完全一致:

输入:s = "aaccb",t = "cacba"
输出:true
解释:两个字符串都包含两个 a、两个 c 和一个 b,只是排列顺序不同。

字符集合相同但频次不同:

输入:s = "abbc",t = "abcc"
输出:false
解释:s 中 b 出现两次而 c 出现一次,t 中这两个频次相反,因此不是字母异位词。

频次守恒

字母异位词只允许重排,不允许增加、删除或替换字符。因此先比较长度;长度相同后, 扫描 s 对对应字母计数加一,扫描 t 减一。若最终所有 26 个计数都为 0, 两串对每个字符的出现次数完全相同;只要某个计数不为 0,就存在字符频次差异。

可以在第二次扫描时一旦发现某个计数变成负数就返回假,但最后统一检查更容易直接对应频次等式。 本题字符域固定为小写 a 到 z,数组下标比哈希表更直接;若题目改为 Unicode,才需要按完整字符单位选择其他映射。

正确性说明

处理完两个字符串后,count[c] 等于字符 c 在 s 中的出现次数减去在 t 中的出现次数。 若所有计数为 0,两边每种字符数量一致,可以把 s 的字符逐个重排成 t;若有非零计数, 至少一种字符数量不同,任何重排都无法得到 t。长度检查覆盖了总字符数不相等的情况。

C++ 实现

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

        int count[26] = {};
        for (char ch : s) ++count[ch - 'a'];
        for (char ch : t) --count[ch - 'a'];

        for (int value : count) {
            if (value != 0) return false;
        }
        return true;
    }
};

代码分析

两次扫描时间复杂度为 O(n),频次数组固定为 26 个整数,额外空间为 O(1)。 代码按题目保证的小写字符域做索引,不修改输入字符串;重复字符会分别计数,不会因集合只保留存在性而丢失频次。