【LeetCode】242. 有效的字母异位词（简单）——代码随想录算法训练营Day06

题目链接：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 * 104
• s?和?t?仅包含小写字母

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

文章讲解：代码随想录

视频讲解：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词_哔哩哔哩_bilibili

题解1：哈希表

思路：题目中的条件有 s 和 t 都是由小写字母组成，而小写字谜 a ~ z 的 ASCII 码是连续的。因此我们可以构建一个长度为26的数组作为哈希数组，存储每个小写字母出现的个数。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    const hashArr = new Array(26).fill(0);
    // 如果 s.length === t.length 直接返回 false
    if (s.length !== t.length) {
        return false;
    }
    for (let i = 0; i < s.length; i++) {
        hashArr[s.charCodeAt(i) - 'a'.charCodeAt()]++;
        hashArr[t.charCodeAt(i) - 'a'.charCodeAt()]--;
    }
    // record数组所有元素都为零0，说明字符串s和t是字母异位词。
    // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
    return hashArr.every(c => c === 0);
};

分析：遍历了两个字符串，额外开辟的哈希数组长度固定为26，时间复杂度为 O(n)，空间复杂度为 O(1)。

收获

当我们需要快速判断一个元素是否出现在集合中、在集合中出现多少次的时候，就可以考虑哈希法。