leetcode.49.字母异位词分组

题目描述

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

示例:

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

说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

标签 哈希表 字符串

https://leetcode-cn.com/problems/group-anagrams/

解法一：哈希表

当且仅当它们的排序字符串相等时，两个字符串是字母异位词。

维护一个哈希映射 ans : {String -> List}，其中每个键 K 是一个排序字符串，每个值是初始输入的字符串列表，排序后等于 K。

时间复杂度：O(NKlogK)，其中 N 是 strs 的长度，而 K 是 strs 中字符串的最大长度。当我们遍历每个字符串时，外部循环具有的复杂度为 O(N)。然后，我们在 O(KlogK) 的时间内对每个字符串排序。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let hash = new Map()
    
    for(let i = 0; i < strs.length; i++) {
        let str = strs[i].split('').sort().join()
        if(hash.has(str)) {
            let temp = hash.get(str)
            temp.push(strs[i])
            hash.set(str, temp)
        } else {
            hash.set(str, [strs[i]])
        }
    }
    
    return [...hash.values()]
};

解法二：利用数学设计键

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

利用这个，我们把每个字符串都映射到一个正数上。

用一个数组存储质数 prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]。
然后每个字符串的字符减去 ‘ a ‘ ，然后取到 prime 中对应的质数。把它们累乘。
例如 abc ，就对应 ‘a’ - ‘a’， ‘b’ - ‘a’， ‘c’ - ‘a’，即 0, 1, 2，也就是对应素数 2 3 5，然后相乘 2 3 5 = 30，就把 “abc” 映射到了 30。
相减时用 Unicode 编码。

和解法一的理论差不多，不过少了字符串的排序。

也就是用另外一种方式解决了哈希设计键。

时间复杂度 O(NK)

var groupAnagrams = function(strs) {
	let res = {};
	for(let i = 0; i < strs.length; i++) {
		const str = strs[i]
		const hash = str.split('').reduce((sum, s)=>{
			return sum * [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103 ][s.charCodeAt(0) - 97]
		}, 1)
		res[hash] ? res[hash].push(str) : res[hash] = [str]
	}
	
	return Object.values(res)

};

解法三：计数

首先初始化 key = “0#0#0#0#0#”，数字分别代表 abcde 出现的次数，# 用来分割。
这样的话，”abb” 就映射到了 “1#2#0#0#0”。
“cdc” 就映射到了 “0#0#2#1#0”。
“dcc” 就映射到了 “0#0#2#1#0”。

然后和其他解法一样，如果 key 一样，就把值映射到对应的 key 里。

时间复杂度：O(NK)。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let hash = new Map()
     
    for(let i = 0; i < strs.length; i++) {
        let str = strs[i]
        let arr = Array(26).fill(0)
        for(let j = 0; j < str.length; j++) {
            arr[str.charCodeAt(j) - 97] ++
        }
        let hashKey = arr.join()
        if(hash.has(hashKey)) {
            let temp = hash.get(hashKey)
            temp.push(str)
            hash.set(hashKey, temp)
        } else {
            hash.set(hashKey, [str])
        }
    }
    return [...hash.values()]
};

所有的方法基本上都是为哈希表设计合适的键

因为需要几个值同时对应同一个键

所以要找到一个合适键的规则