LeetCode之旅——字母異位詞分組（Group Anagrams）

題目

給定一個字符串數組，要求將相同字母組成的字符串分組返回。字符串只由小寫字母組成。

示例：

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

思路一

將輸入的每個字符串拆成字符排序，然後利用Map分組。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map()
    for (let i = 0; i < strs.length; ++i) {
        const key = strs[i].split('').sort().join()
        map.has(key)
            ? map.set(key, map.get(key).concat(strs[i]))
            : map.set(key, [strs[i]])
    }
    return Array.from(map.values())
};

思路二

由於字符串限定只由小寫字母組成，可以構建一個長為26的“桶”，每一格存儲對應的字母出現的次數。這樣，每個字符串都被轉化為一個這樣的桶。然後把“桶”重新轉為字符串，作為Map的鍵對原字符串數組進行分組。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const list = []
    for (const str of strs) {
        //为每个字符串构造一个“桶”
        const layer = []
        for (const s of str) {
            c = s.charCodeAt(0)
            let value = layer[c - 0x60]
            value = value ? value + 1 : 1
            layer[c - 0x60] = value
        }
        list.push(layer.join(' '))
    }
    //把桶字符串化后作为key对原数组进行分组
    const res = new Map()
    for (let i = 0; i < list.length; ++i) {
        res.has(list[i]) 
            ? res.set(list[i], res.get(list[i]).concat(strs[i]))
            : res.set(list[i], [strs[i]])
    }
    return Array.from(res.values())
};

總結

思路一更簡潔，但排序可能會消耗更多的時間。思路二利用了桶排序的思想，將排序復雜度降到了線性復雜度。在字符串較長時思路二應該會表現更好。