---

前言

這是刷算法題的第十七天，用到的語言是JS
題目：力扣 49. 字母異位詞分組 (中等)

---

一、題目內容

給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。

字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。

示例 1:
輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
輸出: [[“bat”], [“nat”, “tan”], [“ate”, “eat”, “tea”]]

示例 2:
輸入: strs = [“”]
輸出: [[“”]]

示例 3:
輸入: strs = [“a”]
輸出: [[“a”]]

提示：

1 <= strs.length <= 10⁴
0 <= strs[i].length <= 100
strs[i] 僅包含小寫字母

二、解題方法

1. 哈希函數

將相同字母的扔到一塊，然后再按照字典序進行排序輸出

代碼如下（示例）：

/*** @param {string[]} strs* @return {string[][]}*/
var groupAnagrams = function(strs) {// 題目的意思？：將相同字母的扔到一塊，然后再按照字典序進行排序輸出？// 我的疑問：怎么做到第一步const map = new Map()const arr = [] // 存放返回的數組for(let i = 0; i < strs.length; i++) {const sort = strs[i].split('').sort().join('') // 排序,將相同字母的字符串排序后，得到相同的字符串map.set(sort, [...(map.get(sort) || []), strs[i]]) // 解釋一下這行代碼：如果map中存在sort，則取出sort對應的數組，將strs[i]放入數組中，如果不存在sort，則新建一個數組，將strs[i]放入數組中// 再人話點：...(map.get(sort)將 值(值數組['eat', 'tea'])展開成 'eat', 'tea'，然后再添加上 strs[i](是ate)，然后就變成了 'eat', 'tea', 'ate'// 將上面這行代碼拆解出來// if(map.has(sort)) {//   map.set(sort, [...map.get(sort), strs[i]])// } else {//   map.set(sort, [strs[i]])// }}for(const [key, value] of map) {arr.push(value)}return arr
}console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

---

2.官方題解

2.1 前言

兩個字符串互為字母異位詞，當且僅當兩個字符串包含的字母相同。同一組字母異位詞中的字符串具備相同點，可以使用相同點作為一組字母異位詞的標志，使用哈希表存儲每一組字母異位詞，哈希表的鍵為一組字母異位詞的標志，哈希表的值為一組字母異位詞列表。

遍歷每個字符串，對于每個字符串，得到該字符串所在的一組字母異位詞的標志，將當前字符串加入該組字母異位詞的列表中。遍歷全部字符串之后，哈希表中的每個鍵值對即為一組字母異位詞。

以下的兩種方法分別使用排序和計數作為哈希表的鍵。

2.2 方法一：排序

由于互為字母異位詞的兩個字符串包含的字母相同，因此對兩個字符串分別進行排序之后得到的字符串一定是相同的，故可以將排序之后的字符串作為哈希表的鍵。

代碼如下（示例）：

var groupAnagrams = function(strs) {const map = new Map();for (let str of strs) {let array = Array.from(str);array.sort();let key = array.toString();let list = map.get(key) ? map.get(key) : new Array();list.push(str);map.set(key, list);}return Array.from(map.values());
};作者：力扣官方題解
鏈接：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

復雜度分析：

時間復雜度： $O(nklogk)$，其中 $n$ 是 $strs$ 中的字符串的數量， $k$ 是 $strs$ 中的字符串的的最大長度。需要遍歷 $n$ 個字符串，對于每個字符串，需要 $O(klogk)$ 的時間進行排序以及 $O(1)$ 的時間更新哈希表，因此總時間復雜度是 $O(nklogk)$。

空間復雜度： $O(nk)$，其中 $n$ 是 $strs$ 中的字符串的數量， $k$ 是 $strs$ 中的字符串的的最大長度。需要用哈希表存儲全部字符串。

鏈接：力扣本題官方題解
來源：力扣（LeetCode）

2.2 方法二：計數

由于互為字母異位詞的兩個字符串包含的字母相同，因此兩個字符串中的相同字母出現的次數一定是相同的，故可以將每個字母出現的次數使用字符串表示，作為哈希表的鍵。

由于字符串只包含小寫字母，因此對于每個字符串，可以使用長度為 26 的數組記錄每個字母出現的次數。需要注意的是，在使用數組作為哈希表的鍵時，不同語言的支持程度不同，因此不同語言的實現方式也不同。

代碼如下（示例）：

var groupAnagrams = function(strs) {const map = new Object();for (let s of strs) {const count = new Array(26).fill(0);for (let c of s) {count[c.charCodeAt() - 'a'.charCodeAt()]++;}map[count] ? map[count].push(s) : map[count] = [s];}return Object.values(map);
};作者：力扣官方題解
鏈接：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

鏈接：力扣本題官方題解
來源：力扣（LeetCode）