当前位置：首页 > article >正文

leetcode242-有效字母异位词

article 2025/1/21 7:00:17

leetcode 242
在这里插入图片描述

什么是字母异位词

字母异位词是指：由相同的字母组成，但字母排列顺序不同的两个字符串。
字母异位词特点：

两个字符串的长度相同
两个字符串中每个字母出现的频次相同

思路

利用哈希表来解决此题，首先创建一个hash map，然后循环s字符串，对每个出现的字母进行记录，如果出现过就+1，没出现过就设置为1，再循环t字符串，如果把每个字母-1，如果-1以后发现当前字母是<0那么可能是两种情况：t中的字母出现了但是s中字母没出现过的，或者t中字母出现的次数大于s中该字母出现的次数，不管是哪一种都是不符合条件的，所以return false
如果t遍历以后都没出现不符合的，这说明是异位词，所以return true;

实现

方法1 hash map

var isAnagram = function(s, t) {
    if(s.length!==t.length) return false;
    const map = new Map();
    for(let i = 0;i<s.length;i++){
        const item = s[i]
        map.set(item,(map.get(item) || 0) + 1);
    }
    for(let i = 0;i<t.length;i++){
        const item = t[i];
        map.set(item,(map.get(item) || 0) - 1);
        if(map.get(item) < 0){
            return false;
        }
    }
    return true;
};

方法2 哈希数组

通过字符串的charCodeAt方法能获取到字母的ASCII编码，字母中从a-z中ASCII编码是递增的，所以我们可以设置‘a’为0，然后总共26个字母，把每个字母的ASCII码-字母a的ASCII码则表示对应在数组中的索引

var isAnagram = function (s, t) {
    if (s.length !== t.length) return false;
    const hashArr = new Array(26).fill(0);
    let ascii_a = 'a'.charCodeAt(); 
    for (let i = 0; i < s.length; i++) {
        const item = s[i].charCodeAt();
        hashArr[item-ascii_a]++;
    }
    for(let i = 0;i < t.length;i++){
        const item = t[i].charCodeAt()
        hashArr[item - ascii_a]--;
        if(hashArr[item-ascii_a] < 0){
            return false
        }
    }
    return true;
};