【数据结构与算法】力扣 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 仅包含小写字母

分析解答

比较字符串内字符的个数相同，很容易想到将各个字符作为一个key 存入一个对象中，个数相同就是这些键值是否相同。

此时会发现存在一个问题：那就是key 的顺序不同也会导致判断不同。所以判断是否相同时需要先将key进行排序。

这种类似于暴力解答，直接进行判断。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
    let sHash = {}
    let tHash = {}
    for (let i = 0; i < s.length; i++) {
        if (!sHash[s[i]]) {
            sHash[s[i]] = 1
            continue
        }
        sHash[s[i]]++
    }
    for (let i = 0; i < t.length; i++) {
        if (!tHash[t[i]]) {
            tHash[t[i]] = 1
            continue
        }
        tHash[t[i]]++
    }
    console.log(JSON.stringify(sHash))
    console.log(JSON.stringify(tHash))
    return isEqual(sHash, tHash)
};

function isEqual(obj1, obj2) {
    // 获取对象的键
    const keys1 = Object.keys(obj1).sort();
    const keys2 = Object.keys(obj2).sort();
    // 检查键的数量
    if (keys1.length !== keys2.length) {
        return false;
    }
    // 检查键的值是否相等
    for (let i = 0; i < keys1.length; i++) {
        const key = keys1[i];
        if (key !== keys2[i] || obj1[key] !== obj2[key]) {
            return false;
        }
    }
    return true;
}

console.log(isAnagram('ab', 'a'))

思路拓展

这里讲一下哈希法。

主要思路：就是在 arr 中放26个位置，值全为0。然后遍历 s，在 a-z 的对应位置加 1，然后遍历 t，在 a-z 的对应位置减 1，所以 s 和 t 相同的话，那么所有位置应该还是 0。

js 这里需要用 charCodeAt 获取 ascii 值。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
    if (s.length !== t.length) {
        return false
    }
    let arr = new Array(26).fill(0);
    const base = 'a'.charCodeAt()
    for (let i of s) {
        arr[i.charCodeAt() - base]++
    }
    for (let i of t) {
        arr[i.charCodeAt() - base]--
    }
    for (let i = 0; i < 26; i++) {
        if (arr[i] != 0) {
            return false
        }
    }
    return true
};