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())
};

总结

思路一更简洁，但排序可能会消耗更多的时间。思路二利用了桶排序的思想，将排序复杂度降到了线性复杂度。在字符串较长时思路二应该会表现更好。