# 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.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

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

```javascript
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` 運算了

```javascript
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 位置**

```javascript
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](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Array/sort) 函式預設為根據字串的 Unicode 編碼位置進行排序，所以不用再傳入參數排序

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

或是使用 [charCodeAt](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt) 也跟上面一樣

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

### 相關題目

{% embed url="<https://bcjohnblue.gitbook.io/leetcode/242.-valid-anagram>" %}

### 測資

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

console.log(groupAnagrams(strs))
```
