【算法】有效的字母异位词

难度：简单
题目：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
1
2

示例 2:

输入: s = "rat", t = "car"
输出: false
1
2

提示:

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

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

解题思路一：
要判断两个字符串s和t是否是字母异位词，核心思想是检查两个字符串中每个字符出现的次数是否完全相同。

1. 检查长度：首先检查两个字符串的长度是否相等，如果不等，立即返回false，因为长度不等的两个字符串不可能是字母异位词。
2. 统计字符频率：创建一个计数器（可以是一个对象或数组，考虑到ASCII码的范围，通常使用数组更为高效）。遍历第一个字符串s，对于s中的每个字符，增加计数器中相应位置的计数值。
3. 验证字符频率：接着遍历第二个字符串t，对于t中的每个字符，减少计数器中相应位置的计数值。如果在减的过程中发现计数值变为负数，说明t中某字符的数量比s多，立即返回false。
4. 检查计数器：最后检查计数器中的所有值是否都为0，如果是，则s和t是字母异位词，否则不是。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // 如果长度不同，直接返回 false
    if (s.length !== t.length) {
        return false;
    }
    // 初始化计数器数组，假设字符集为小写字母，ASCII码范围是97到122
    const counter = new Array(26).fill(0);

    // 增加s中字符的计数
    for (let char of s) {
        counter[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    // 减少t中字符的计数
    for (let char of t) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        if (--counter[index] < 0) {
            return false;
        }
    }

    // 检查计数器中所有值是否为0
    for (let count of counter) {
        if (count !== 0) {
            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
29
30
31
32
33
34
35

解题思路二：
针对字母异位词的问题，还有一种较为直观且高效的解法，那就是使用哈希映射（在 JavaScript 中通常是对象或 Map）。这种方法可以避免对计数器数组的直接操作，使得代码更加灵活，易于理解和维护。

1. 初始化两个哈希映射：分别用于存储字符串 s 和 t 中每个字符的出现次数。
2. 遍历字符串：遍历字符串 s和 t，在哈希映射中记录每个字符的出现次数。
3. 比较哈希映射：最后比较两个哈希映射是否完全相同。如果两个哈希映射中每个键和对应的值都相同，则 s 和 t 是字母异位词。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const mapS = {}, mapT = {};

    // 同时构建两个哈希映射
    for (let i = 0; i < s.length; i++) {
        mapS[s[i]] = (mapS[s[i]] || 0) + 1;
        mapT[t[i]] = (mapT[t[i]] || 0) + 1;
    }

    // 直接比较两个映射
    for (let key in mapS) {
        if (mapS[key] !== mapT[key]) {
            return false;
        }
    }

    // 确保 t 中的每个字符也在 s 中出现相同的次数
    for (let key in mapT) {
        if (mapS[key] === undefined) {
            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
29
30
31
32
33
34

解题思路三：
要判断两个字符串s和t是否是字母异位词，核心思想是检查两个字符串中每个字符出现的次数是否完全相同。

1. 检查长度：首先检查两个字符串的长度是否相等，如果不等，立即返回false，因为长度不等的两个字符串不可能是字母异位词。
2. 字符串排序：对两个字符串进行排序。
3. 比较：比较两个字符串是否相等，如果相等，直接返回true，不相等，返回false。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // 如果长度不同，直接返回 false
    if (s.length !== t.length) {
        return false
    }
    // 字符串排序
    let sString = s.split('').sort().join(''),
    tString = t.split('').sort().join('')
    // 比较
    return sString == tString ? true : false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16