leetcode 面试经典 150 题：有效的字母异位词

链接	有效的字母异位词
题序号	242
题型	字符串
解法	哈希表
难度	简单
熟练度	✅✅✅

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

提示:
1 <= s.length, t.length <= 5 * 10⁴
s 和 t 仅包含小写字母

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

题解

字母异位词：它们包含相同字符，并且每个字符出现的次数也相同。
核心思想：使用哈希表来解决“有效的字母异位词”问题是一种非常直观和高效的方法。基本思路是通过哈希表来记录每个字符的出现次数，然后比较两个字符串的字符计数是否相同。
复杂度：时间复杂度O(n)，空间复杂度O(1)。
c++ 实现算法：

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false; // 长度不同直接返回 false

    unordered_map<char, int> count;
    
    for (char c : s) count[c]++; // 统计 s 中每个字符的出现次数
    
    for (char c : t) {
        if (count[c] == 0) return false; // 如果字符 c 的计数为 0，说明 t 多出字符
        count[c]--; // 减少对应字符的计数
    }

    return true;
}

算法推演：

输入及初始化
string s = “anagram”; string t = “nagaram”;

检查长度：
if (s.length() != t.length()) return false; s.length() =7，t.length() = 7，长度相等，继续执行。
初始化哈希表：
unordered_map<char, int> count; 创建一个空的哈希表 count，用于存储 s 中每个字符的频率。

遍历字符串 s，统计字符频率
for (char c : s) count[c]++;
遍历字符串 s = “anagram”：
遇到 ‘a’，count[‘a’] = 1
遇到 ‘n’，count[‘n’] = 1
遇到 ‘a’，count[‘a’] = 2
遇到’g’，count[‘g’] = 1
遇到 ‘r’，count[‘r’] = 1
遇到 ‘a’，count[‘a’] = 3
遇到’m’，count[‘m’] = 1

最终哈希表状态： count = {
‘a’: 3,
‘n’: 1,
‘g’: 1,
‘r’: 1,
‘m’: 1 }

遍历字符串 t，验证字符频率
for (char c : t) {
if (count[c] == 0) return false;
count[c]–;
}
遍历字符串 t = “nagaram”，逐步验证 t 中的字符是否匹配：

第 1 个字符 ‘n’：
检查 count[‘n’]，当前值为 1（非 0）。将 count[‘n’]–，更新为 0。
哈希表状态：
count = {
‘a’: 3,
‘n’: 0,
‘g’: 1,
‘r’: 1,
‘m’: 1 }

第 2 个字符 ‘a’：
检查 count[‘a’]，当前值为 3（非 0）。将 count[‘a’]–，更新为 2。
哈希表状态：
count = {
‘a’: 2,
‘n’: 0,
‘g’: 1,
‘r’: 1,
‘m’: 1 }

第 3 个字符 ‘g’：检查 count[‘g’]，当前值为 1（非 0）。将 count[‘g’]–，更新为 0。
哈希表状态：
count = {
‘a’: 2,
‘n’: 0,
‘g’: 0,
‘r’: 1,
‘m’: 1 }

第 4 个字符 ‘a’：检查 count[‘a’]，当前值为 2（非 0）。将 count[‘a’]–，更新为 1。
哈希表状态：
count = {
‘a’: 1,
‘n’: 0,
‘g’: 0,
‘r’: 1,
‘m’: 1 }

第 5 个字符 ‘r’：检查 count[‘r’]，当前值为 1（非 0）。将 count[‘r’]–，更新为 0。
哈希表状态：
count = {
‘a’: 1,
‘n’: 0,
‘g’: 0,
‘r’: 0,
‘m’: 1 }

第 6 个字符 ‘a’：检查 count[‘a’]，当前值为 1（非 0）。将 count[‘a’]–，更新为 0。
哈希表状态：
count = {
‘a’: 0,
‘n’: 0,
‘g’: 0,
‘r’: 0,
‘m’: 1 }

第 7 个字符 ‘m’：检查 count[‘m’]，当前值为 1（非 0）。将 count[‘m’]–，更新为 0。
哈希表状态：
count = {
‘a’: 0,
‘n’: 0,
‘g’: 0,
‘r’: 0,
‘m’: 0 }

验证完成遍历字符串 t 的所有字符后，未提前返回 false。哈希表中所有字符的计数均为 0，说明 s 和 t 是字母异位词。

返回结果 return true; 输出结果为 true，即 s = “anagram” 和 t = “nagaram” 是字母异位词。

c++ 完整 demo：

#include <iostream>
#include <unordered_map>
using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false; // 长度不同直接返回 false

    unordered_map<char, int> count;
    
    for (char c : s) count[c]++; // 统计 s 中每个字符的出现次数
    
    for (char c : t) {
        if (count[c] == 0) return false; // 如果字符 c 的计数为 0，说明 t 多出字符
        count[c]--; // 减少对应字符的计数
    }

    return true;
}

int main() {
    string s = "anagram";
    string t = "nagaram";
    cout << (isAnagram(s, t) ? "True" : "False") << endl;
    return 0;
}