49. Group Anagrams

Leetcode

https://leetcode.com/problems/group-anagrams/

題目

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

解答

• 方法一

利用 Leetcode 242. 的解答方法，再額外加判斷

var groupAnagrams = function(strs) {
    var isAnagram = function(s, t) {
        if(s.length != t.length) return false;
        const hash1 = {};
        const hash2 = {};
        for(let i=0; i<s.length; i++) {
            const value1 = s[i];
            if(hash1[value1]) hash1[value1]++;
            else hash1[value1] = 1;

            const value2 = t[i];
            if(hash2[value2]) hash2[value2]++;
            else hash2[value2] = 1;
        }

        for(let key of Object.keys(hash1)) {
            if(hash1[key] !== hash2[key]) return false;
        }
        return true;
    };
    
    const arr = []
    for(let i=0; i<strs.length; i++) {
        let isMatch = false;
        for(let j=0; j<arr.length; j++) {
            if(isAnagram(strs[i], arr[j][0])) {
                isMatch = true;
                arr[j].push(strs[i]);
                break;
            }
        }
        if(!isMatch) arr.push([strs[i]]);
    }
    return arr;
};

Time Limit Exceeded

• 方法二 - 添加 hashCode

方法一因為使用雙迴圈運算，而且每輪都需要執行 isAnagram 判斷最終會耗時過長，所以我們額外新增一個 generateHashCode 的函式，紀錄字串進行 hashCode 後的結果，如果兩個字串 hashCode 不一樣的話就不用再執行 isAnagram 運算了

var groupAnagrams = function(strs) {
    var isAnagram = function(s, t) {
        if(s.length != t.length) return false;
        const hash1 = {};
        const hash2 = {};
        for(let i=0; i<s.length; i++) {
            const value1 = s[i];
            if(hash1[value1]) hash1[value1]++;
            else hash1[value1] = 1;

            const value2 = t[i];
            if(hash2[value2]) hash2[value2]++;
            else hash2[value2] = 1;
        }

        for(let key of Object.keys(hash1)) {
            if(hash1[key] !== hash2[key]) return false;
        }
        return true;
    };

    const generateHashCode = (str) => {
      let hashCode = 0; 
      for(let i=0; i<str.length; i++) {
        hashCode += str.charCodeAt(i);
      }
      return hashCode;
    };
    
    const arr = []
    for(let i=0; i<strs.length; i++) {
        const str = strs[i];
        const hashCode = generateHashCode(str);
        let isMatch = false;
        for(let j=0; j<arr.length; j++) {
          const target = arr[j];
          if(hashCode !== target.hashCode) continue;
          if(isAnagram(str, target.value[0])) {
              isMatch = true;
              arr[j].value.push(str);
              break;
          }
        }
        if(!isMatch) {
          arr.push({value: [str], hashCode});
        }
    }
    return arr.map(arr => arr.value);
};

Runtime: 536 ms, faster than 5.95% of JavaScript online submissions for Group Anagrams.

Memory Usage: 60.7 MB, less than 5.05% of JavaScript online submissions for Group Anagrams.

• 方法三 - 利用內建的 sort 排序字母，當作 map 的 key

可以看到以上的方法計算的時間還是很久，為了拿空間換取時間，我們可以創建一個 hashmap，hashmap 中的 key 紀錄的是排序過的字串，value 則是對應到該 排序過的字串 所在 矩陣的 index 位置

var groupAnagrams = function (strs) {
    const ans = [];
    const map = {};

    for (let i = 0; i < strs.length; i++) {
        const str = strs[i];
        const key = str.split('').sort().join('');
        const index = map[key];
        if (index !== undefined) {
            ans[index].push(str);
        } else {
            ans.push([str]);
            map[key] = ans.length - 1;
        }
    }

    return ans;
};

Runtime: 102 ms Beats 90.46% of users with JavaScript

Memory: 61.84 MB Beats 87.95% of users with JavaScript

時間複雜度：O(n) => 只遍歷 strs 矩陣一次

空間複雜度：O(n) => ans 矩陣

說明

sort 函式預設為根據字串的 Unicode 編碼位置進行排序，所以不用再傳入參數排序

'bca'.split('').sort().join('') => 'abc'

或是使用 charCodeAt 也跟上面一樣

'bca'.split('').sort((a, b) => a.charCodeAt(0) - b.charCodrAt(0)).join('') => 'abc'

相關題目

242. Valid Anagram | Leetcodebcjohnblue.gitbook.io

測資

let strs = ["eat","tea","tan","ate","nat","bat"];
strs = [""];
strs = ["a"];

console.log(groupAnagrams(strs))