242. 有效的字母异位词（力扣LeetCode）

242. 有效的字母异位词

题目描述

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

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

示例 2:

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

提示:

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

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

c++代码

代码执行流程如下：

1. 首先，通过比较两个字符串 s 和 t 的长度，如果它们长度不相等，则直接返回 false，因为不同长度的字符串不可能是异位词。
2. 声明两个长度为26的整型数组 a 和 b，用于计算每个字符串中每个字母的出现频率。这里使用一个小技巧：由于题目说明只包含小写字母，可以通过减去 ‘a’ 的 ASCII 值将字母的 ASCII 值映射到一个 0 到 25 的范围内，这样 a[0] 就对应 ‘a’ 的出现次数，a[1] 对应 ‘b’ 的出现次数，以此类推。
3. 使用两个独立的循环分别遍历字符串 s 和 t，并递增 a 和 b 数组中相应字母计数器的值。
4. 使用一个循环比较两个计数器数组 a 和 b 的每一个元素。如果所有元素都相等，则说明 s 和 t 有相同的字符和频率，可以认为它们是异位词，函数返回 true。如果有任何一个元素不相等，函数返回 false。

进阶情况
对于包含 Unicode 字符的字符串，我们不能仅仅使用长度为26的数组来计数，因为 Unicode 字符集非常大。一个可能的解决方案是使用 unordered_map（或 map，取决于性能要求）来动态地存储每个字符及其出现的次数。这样我们就可以支持所有 Unicode 字符，而不仅限于26个小写英文字母。

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 如果两个字符串长度不同，它们不能是异位词
        if(s.size() != t.size()) return false;
        
        // 声明两个长度为26的数组来计数字母出现频率
        // 英文字母表大小为26
        int a[26] = {0}, b[26] = {0};
        
        // 遍历字符串s，统计每个字母出现的次数
        for(int i = 0; i < s.size(); i++)
            a[s[i] - 'a']++; // 'a'的ASCII码作为偏移量，将字母映射到0-25的范围
        
        // 遍历字符串t，统计每个字母出现的次数
        for(int i = 0; i < t.size(); i++)
            b[t[i] - 'a']++; // 同上
        
        // 比较两个数组的内容是否完全一致
        for(int i = 0; i < 26; i++)
            // 如果在某个字母的计数不同，则不是异位词
            if(a[i] != b[i])
                return false;
        
        // 如果所有字母计数都相同，则是有效的异位词
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28