leetcode49

字母异位词分组

题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

分析

最简单解法:

思路:1 用hashMap存对应键的值到数组,最终选取Map.values()

const groupAnagrams = function (strs) {
    const hash = new Map(), n = strs.length
    for (let i = 0; i < n; i++) {
        let key = Array.from(strs[i])
        key.sort()
        key = key.toString()
        let list = hash.get(key)? hash.get(key): new Array()
        list.push(strs[i])
        hash.set(key, list)
    }
    return Array.from(hash.values())
};

时间复杂度: O(nmlgm), 其中n为数组长度,m为键长度,因为这里要将每个key排序

方法2:计数

思路:由于本题给的数据范围在26个小写字母,所以可以新建长度为26的Array,作为唯一key,存入hash表中,降低sort()的时间复杂度