今天是LeetCode专题的第30篇文章，一起来看一道字符串分组的问题。
题意
这题的题意很简单，给定一个字符串数组，要求将所有字符串按照构成分组。
举个例子，比如给定的数组是[eat, ate, tea, tan, nat, bat]。
其中eat，ate，tea这三个单词用到的字母都是e，t和a各一个。tan和nat用到的都是a，n和t，后剩下bat，所以分组结果就是：[eat, ate, tea]，[tan, nat]和[bat]。
暴力
我们依然从简单的思路开始想起，我们分组的依据是每一个字符串当中用到的字母的情况。所以我们可以把每一个字符串当中所有的元素拆解出来，放到一个dict当中，然后我们用这个dict来作为分组的标准，将dict相同的字符串放在同一组。
比如eat我们把它变成{'e': 1, 'a': 1, 't': 1}，由于一个字母可能出现多个，所以我们也要记录出现的次数。但有一个问题是，dict是动态数据，在Python当中我们不能用它作为另一个dict的key。这个问题比较简单的方法是我们写一个方法将这个dict拼接成字符串，比如'e1a1t1'。我们用这个作为key。但是这又有了一个问题，dict当中的key并不一定是有序的，所以我们需要对dict进行排序，可以看下下图中的流程。
也就是说我们需要实现一个函数，它的输入是字符串，输出是这个字符串构成的元素。
def splitStr(s):
d = defaultdict(int)
for c in s:
d[c] += 1
ret = ''
# 将dict中内容排序
for k,v in sorted(d.items()):
ret += (str(k) + str(v))
return ret
到这里就简单了，我们在外层再创建一个dict用来存储分组后的结果即可，我们很容易就能写出代码：
from collections import defaultdict
class Solution:
def splitStr(self, s):
d = defaultdict(int)
# 拆分字符串中元素
for c in s:
d[c] += 1
ret = ''
# 将dict中内容排序
for k,v in sorted(d.items()):
ret += (str(k) + str(v))
return ret
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
# 拿到拆分之后的字符串作为key进行分组
key = self.splitStr(s)
groups[key].append(s)
ret = []
for _, v in groups.items():
ret.append(v)
return ret
有些小伙伴可能意识到了一个问题，既然我们先转化成dict之后后面还是要拼接成字符串，我们为什么不直接对字符串排序，将排序之后的结果作为key呢？构成元素一样的字符串，排序之后的结果必然是相同的。
比如apple和pplae排序之后都是aelpp，这样可行吗？
思路是OK的，但是提交并不能通过。原因也很简单，三个字可以概括，就是复杂度。这样做的复杂度非常大，因为字符串的长度并不是固定的，我们对它们一一排序需要大量的开销。另外我们用排序之后的结果作为key，也会占用存储资源。所以这不是一个好方法。
hash
接下来就到了我们的正主出场了，大家从标题当中应该就已经看出来了，这道题和hash算法有关。
讲道理，hash算法的名称如雷贯耳，我们经常听到，但是很多人并不知道hash算法是干嘛的，或者我们究竟什么地方要用到它。大家听得比较多的可能是hashMap。
其实hash算法的内容很简单，可以简单理解成映射。我们的输入可以是任何内容，可以是一个数字，也可以是个数组或者是一个对象，但是我们的输出是一个固定若干个字节组成的信息。比如下图当中对4取模就是一个hash函数，我们可以根据对4取模之后的结果将数归类到不同的分桶当中。
我们可以按照我们的意愿让一些数据分在同一个分桶当中，我们也可以让每一条数据hash之后的结果都尽量各不相同，这样做实现的是信息的压缩。比如我们将一个大小2MB的实例进行hash，得到了一个32位的字符串。相当于我们用32位的字符串就可以代表原本2MB的内容，这样我们可以进行高效的查询或者是其他操作。举个例子，比如当下的人脸识别模块，就可以简单理解成一个hash函数。摄像头拍摄照片，算法将照片hash成一个id，再去数据库当中找到这个id对应的个人信息，完成识别过程。
在这道题当中，我们希望设计一个hash函数，它读入一个字符串，根据字符串当中的内容进行hash，保证构造相同的字符串hash得到的结果一致。我们就通过这个hash之后的结果来进行分桶，从本质上来说，上面这一种做法也可以看成是一种hash方法。但是由于涉及到了排序，稍稍复杂了一些，并且后返回的是一个字符串，从时间复杂度和空间复杂度上来看，都还有优化的空间，下面我们就来看一个比较常用的hash算法。
在这个算法当中，我们会选择一个质数作为hash因子，这样发生hash碰撞的概率会比较低。通过质数的幂来构造hash结果，我们来看代码：
def hash(dict):
ret =
prime = 23
# k代表字符，v表示出现次数
for k, v in dict:
ret += v * pow(23, ord(k) - ord('a'))
# 对2^32取模，控制返回值在32个bit内
ret %%= (1 << 32)
return ret
这里的ord是取ascii码的运算，即将英文字母转成数字。我们用某一个质数不同的幂来表示不同的字母，再乘上字母出现的次数作为系数。后将每个字母hash的值累加起来就得到了整个字符串的hash值，构造相同的字符串的系数和幂都是一样的，那么后求和的结果显然也会相等，这个结论没有问题。但是反过来，hash值相等的字符串真的一样吗？
from collections import defaultdict
import math
class Solution:
def splitStr(self, s):
hashtable = [ for _ in range(30)]
ret =
for c in s:
hashtable[ord(c) - ord('a')] += 1
# hash算法
for i in range(26):
ret = ret * 23 + hashtable[i]
# 控制返回值在32个bit内
ret %%= (1 << 32)
return ret
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
key = self.splitStr(s)
groups[key].append(s)
ret = []
for _, v in groups.items():
ret.append(v)
return ret
