LeetCode-49-字母异位词分组

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

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

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

按排序字母分类

字母异位词的字母相同，排列不同。题目是要求按字母异位词分组，需要以Map来存储，以一个可以标识字母异位词的标识符作为key，value则为一个数组，满足该key的都被加入到这个数组中。

所以我们的关键就是找准key，一个比较简单的方案就是将字符串按字母进行排序，这样字母异位词由于字母相同，得到的排序字符串一定是相同的。

具体的实现代码如下：

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams1 = function(strs) {
    let map = new Map();
    for (let i = 0; i < strs.length; i ++) {
        // 排序后的字符串作为key
        let key = strs[i].split('').sort((a,b) => a > b ? 1 : -1).join('');
        if (map.get(key)) {
            // 如果已经有该key的存在，则追加到key对应的数组中
            map.get(key).push(strs[i]);
        } else {
            // 否则创建新的key
            map.set(key, [strs[i]])
        }
    }
    // map转换为数组
    return [...map.values()];
};

测试：

let start = new Date();
const test = groupAnagrams1;
console.log(test(["eat", "tea", "tan", "ate", "nat", "bat"])); // [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
console.log(new Date().getTime() - start.getTime()); // 11

时间复杂度： 排序的时间复杂度为$O(KlogK)$，其中K为数组中最长字符串的长度。外层遍历的时间复杂度为$O(N)$，其中N为数组的长度。所以总的时间复杂度为$O(NKlogK)$
空间复杂度： 原数组被存储在了Map中，空间复杂度为$O(NK)$

按字母计数分类

仍然是以Map的形式存储，但key我们不选择对字符串进行排序，因为其时间复杂度较高。

因为字符串中所有字母都是小写字母，总共只有26个，所以我们可以用一个长度为26的数组来记录每个字母的长度，这样只需要一次遍历就能得到一个字符串的key。

具体的实现代码如下：

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams2 = function(strs) {
    let map = new Map();
    let aCharCode = 'a'.charCodeAt(0); // 记录字母a的ascii值
    for (let i = 0; i < strs.length; i ++) {
        // 记录每个字母出现的次数
        let key = new Array(26).fill(0);
        for (let j = 0; j < strs[i].length; j ++) {
            key[strs[i].charCodeAt(j) - aCharCode] ++;
        }
        // 将次数字母转换为字符串作为key
        key = key.join('#');
        // 以下逻辑与上一方法相同
        if (map.get(key)) {
            map.get(key).push(strs[i]);
        } else {
            map.set(key, [strs[i]])
        }
    }
    return [...map.values()];
};

测试：

let start = new Date();
const test = groupAnagrams2;
console.log(test(["eat", "tea", "tan", "ate", "nat", "bat"])); // [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
console.log(new Date().getTime() - start.getTime()); // 8

时间复杂度： 寻找字符串的key只需要一次遍历，所以总时间复杂度降为了$O(NK)$
空间复杂度： 空间复杂度为$O(NK)$

本文由 李海平 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 12,2019