题目描述：

QQ截图20190314100238.png

思路1解析

本题可以通过数学当中的质数的原理进行求解。

质数原理：任何一个和数都可以分解成唯一的一种质数相乘的形式。

例如: 4 可以分解成质数2X2的形式。15可以分级成3乘以5，所以如果将26个字母采用不同质数进行编码。则任何相同字母的任意组合的字符串的编码的乘积一定是一样的。或者也可以说一个字符串最后的编码（和数）都可以分解成不同字母（质数）的组合。而且只要字母组成相同（字母内容和个数相同）最后的字符串的编码一定相同。
本题当中可以对26字母采用不同的质数进行编码，然后构造一个编码列表。对于输入进来的字符串可以先将其字母取出并逐一映射到质数整个字符串的编码为每个字母编码的乘积。
字母编码：{'a': 2, 'c': 5, 'b': 3, 'e': 11, 'd': 7, 'g': 17, 'f': 13, 'i': 23, 'h': 19, 'k': 31, 'j': 29, 'm': 41, 'l': 37, 'o': 47, 'n': 43, 'q': 59, 'p': 53, 's': 67, 'r': 61, 'u': 73, 't': 71, 'w': 83, 'v': 79, 'y': 97, 'x': 89, 'z': 101}
则ate eat 的字符串编码都是2×71×11，相同的编码的字符串映射到同样集合即可。

思路2解析：

先将字符串拆解成单一字母集合，然后将集合进行排序后重新组合成字符串。这样相同组合字符串最后的字符串形式是相同的。例如‘acb’ , 'bca' 最后都调整为‘abc’.
最后再采用哈希的表的形式进行分组即可。

具体代码

1.思路一的具体实现：

def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        import math
        def func_get_prime(n):
             return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i ==0], range(2,n+1))
        primeN =  func_get_prime(102)
        d=dict()
        for i in range(26):
            d[chr(97+i)]=primeN[i]
        
        def strid(s):
            res = 1 
            for c in s:
                res=res*d[c]
            return res
        res ={}
        for s in strs:
            id= strid(s)
            #print id
            if id not in res:
                res[id]=[]            
            res[id].append(s)
        return res.values()

2.思路二的实现

def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        hash_map = {}
        for s in strs:
            sort_s = "".join(sorted(s))
            if sort_s not in hash_map:
                hash_map[sort_s] = [s]
            else:
                hash_map[sort_s].append(s)
    
        return hash_map.values()

复杂度分析

思路一采用的是哈希表和逐行扫描处理的操作所以总的操作复杂度O（N），思路二中采用哈希表和排序操作，排序操作如果采用快拍类操作复杂度为O(N×Log(N)) 所以最终复杂度是： O(N×Log(N)) 要大于思路一。

最后编辑于：2019.03.14 10:32:34