49：字母异位词分组

问题描述

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

示例：

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

说明：

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

问题分析：

这题目的一个朴素的思路就是，先选定第一个元素，然后找到这个strs中与它相等的strs，存储到临时的结果数组中，遍历结束，更新strs数组。继续遍历，到strs数组为空为止。

但是这种办法要对strs遍历n次。如果对于数据量很大且元素各不相同的数据来说，时间复杂度大概是O(nⁿ)。怎么应对这种场景降低时间复杂度呢？我们需要在一次遍历就搞定。

我们对于这种判断相等元素的集合的一个朴素的思路就是用map。把相同特征的元素映射到一个map就可以了。咋弄呢？我们可以对每个元素进行一下排序，这样的话，如果是应该映射到一个map中，他们就应该长一个样子。这也是我们解决问题的总思路。就算我们用别的什么花里胡哨的解法，这个思路是不会变的。

想想还有别的思路吗？听说从数论里有一个比较好的理论。可惜我数学太菜不懂，只能强记+照搬了。

整数的唯一分解定理：一个大于1的整数一定可以被分解成若干质数的乘积，即X=e1^k1 * e2^k2 * …… * en^kn=mul{ei*ki | 1<= i <= n}，X >= 2，e是质数。

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

但是这种方法不如刚才的思路，为啥呢？因为它需要26个质数啊，我们又不是电脑，怎么记得住？？ 而且就算我们写代码赋值，那也挺麻烦的，我们万一写的素数筛有BUG，乐子就大了，自己把自己玩死了。

AC代码1：映射到字符串中。

class Solution:
    def groupAnagrams(self, strs):
        res = []
        ans = dict()
        for i in strs:
            cur_i = ''.join(sorted(i))
            if cur_i in ans:
                ans[cur_i].append(i)
            else:
                ans[cur_i] = [i]
        for i in ans:
            res.append(ans[i])

AC代码2，用素数筛+劳什子唯一定理：

class Solution:
    def groupAnagrams(self, strs):
        res = []
        dicts = dict()
        ans = dict()
        def init():
            count = 0
            for i in range(2,1000):
                flag = True
                for j in range(2,int(i**0.5)+1):
                    if i % j == 0:
                        flag = False
                        break
                if flag:
                    dicts[chr(ord('a')+count)] = i
                    count += 1
                if count == 26:
                    break
        init()
        for i in strs:
            keys = 1
            for j in i:
                keys *= dicts[j]
            if keys in ans:
                ans[keys].append(i)
            else:
                ans[keys] = [i]
        for i in ans:
            res.append(ans[i])
        return res