LeetCode《初級演算法》字串之有效的字母異位詞 -- JavaScript

語言: CN / TW / HK

題目

題目連結:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/

image.png

題解


1、先給字串排序,再比較

因為在 JavaScript 中,字元是以 Unicode 編碼,所以可以先將字串轉換成字元陣列,然後再對字元陣列排序,如果兩字串排序後的結果一樣,則兩字串互為字母異位詞; ```js /* * @param {string} s * @param {string} t * @return {boolean} / var isAnagram = function(s, t) {

if(s.length !== t.length) {
    return false;
}

let sArr = s.split(''),
    tArr = t.split('');

// 排序
sArr.sort(function(a,b){
    return a.charCodeAt()-b.charCodeAt();
});
tArr.sort(function(a,b){
    return a.charCodeAt()-b.charCodeAt();

});

// 對比排序結果
if(sArr.toString() === tArr.toString()) {
    return true;
}else {
    return false;
}

};

```


2、藉助輔組空間記錄兩個字串

一看到題目,我就想先遍歷兩個字串一遍,使用 普通物件 或 Map 記錄分別每個字母出現的次數,如果得到的 普通物件 或 Map 相同,則兩個字串互為異位詞;

```js /* * @param {string} s * @param {string} t * @return {boolean} / var isAnagram = function(s, t) {

if(s.length !== t.length) {
    return false;
}

let sMap = new Map(),
    tMap = new Map();

for(let item of s) {

    if(sMap.get(item) === undefined) {
        sMap.set(item,1);
    }else {
        sMap.set(item,sMap.get(item) + 1);
    }
}

for(let item of t) {

    if(tMap.get(item) === undefined) {
        tMap.set(item,1);
    }else {
        tMap.set(item,tMap.get(item) + 1);
    }
}

// 判斷兩個Map是否相等並不能使用 === ,於是採用如下從一個Map中逐個取出屬性,然後看另一個物件中是否有對應屬性
for(let [key,value] of sMap) {

        if( tMap.get(key) === undefined || tMap.get(key) !== value) {

                return false;
        }
}
return true;

}; ```

改進

上面的方法使用了兩個 Map,下面只使用一個 Map; 一個迴圈 Map 將字串中各字元出現的次數記錄下來,另一個迴圈將另一個字串中的各字元遍歷,如果 Map 中存有相應字元,就對對應的個數減1,直到個數為0就將這個屬性從 Map 中刪除;如下:

```js /* * @param {string} s * @param {string} t * @return {boolean} / var isAnagram = function(s, t) {

if(s.length !== t.length) {
    return false;
}

let sMap = new Map();

    // 新增 Map 中的 屬性
for(let item of s) {

    if(sMap.get(item) === undefined) {
        sMap.set(item,1);
    }else {
        sMap.set(item,sMap.get(item) + 1);
    }
}

    // 刪除 Map 中的 屬性
for(let item of t) {

    let value = sMap.get(item);
    if(value !== undefined) {

        sMap.set(item,value - 1)
        if(sMap.get(item) === 0) {
            sMap.delete(item);
        }
    }else {
        return false;
    }
}

if(sMap.size === 0) {
    return true;

}else {
    return false;
}

}; ```


大家如果有更好的思路和解法,歡迎大家一起來討論啊~

這是使用 JavaScript 對 LeetCode《初級演算法》的每道題的總結和實現的其中一篇,彙總篇在這裡:

https://juejin.cn/post/7006692002125316103