Day 10 字母异位词分组

设计哈希表时，选择合适的键是一门艺术。

这次 「Day 10：字母异位词分组」 打卡题来训练一下，如何为哈希表设计合适的键。

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

示例:

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

输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

补全下面代码：

class Solution:

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

l =  ["eat", "tea", "tan", "ate", "nat", "bat"]
result = {}

for i in l:
    count = [0] * 26
    for c in i:
        count[ord(c) - ord('a')] +=1
    result[str(count)] = result.get(str(count),[]) +[i]
print(result.values())

原本使用sum(ord([c for c in i])来做键值，却没想到不同的字母，sum值是会相同的，看了大佬的解法，才是比较靠谱的。
共看到三解法：

1. [0]*26 占位
2. 用26个质数取代26个字母，字母相乘的结果做为键值
3. 对字母sort，把sort的结果做为键值
   三种解法的汇总如下：

from functools import reduce
import timeit

def solution1():
    word_lists =  ["eat", "tea", "tan", "ate", "nat", "bat"]
    result = {}
    for word in word_lists:
        count = [0] * 26
        for c in word:
            count[ord(c) - ord('a')] +=1
        result[str(count)] = result.get(str(count),[]) +[word]
    print(result.values())

def solution2():
    # 每个字母使用一个质数代表，求每个单词中质数的乘积
    # 乘积相同，单词中的字母相同
    word_lists =  ["eat", "tea", "tan", "ate", "nat", "bat"]
    result = {}
    primes = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19,
        'i': 23, 'j': 29, 'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59,
        'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89, 'y': 97, 'z': 101}

    for word in word_lists:
        count = reduce(lambda x,y:x*y, [primes.get(c) for c in word])
        result[count] = result.get(count,[]) +[word]
    print(result.values())


def solution3():
    word_lists =  ["eat", "tea", "tan", "ate", "nat", "bat"]
    result = {}
    for word in word_lists:
        count = str(sorted(word))
        result[count] = result.get(count,[]) +[word]

    print(result.values())

if __name__ =='__main__':
    word_lists =  ["eat", "tea", "tan", "ate", "nat", "bat"]
    for i in range(1,4):
        func_name = 'solution' + str(i) + '()'
        print(func_name)
        eval(func_name)
        print(timeit.timeit(number=100000000))
        print('*'*40)


solution1()
dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])
0.916411432
****************************************
solution2()
dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])
0.907099799
****************************************
solution3()
dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])
0.9067765050000003
****************************************
python3 groupanagrams.py  2.69s user 0.03s system 98% cpu 2.772 total