leetcode 49 最优解排序 哈希+字典+质数

解法一：
容易想到用Counter计数然后作为key放进字典，但字典不能被hash，所以只能用桶再转tuple，代码如下：

classSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:d={}forsinstrs:bm=[0for_inrange(26)]forcins:bm[ord(c)-ord('a')]+=1bm=tuple(bm)ifbmind:d[bm].append(s)else:d[bm]=[s]ret=[]forkeyind:ret.append(d[key])returnret

优化一：defaultdict
做题做多了也会发现很烦的东西，比如字典每次都要看在不在里面，defaultdct会返回默认值，如果不在的话，不用再加if了，很舒服，代码如下：

fromcollectionsimportdefaultdictclassSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:d=defaultdict(list)forsinstrs:bm=[0for_inrange(26)]forcins:bm[ord(c)-ord('a')]+=1bm=tuple(bm)d[bm].append(s)ret=[]forkeyind:ret.append(d[key])returnret

解法二：质数
由于质因数分解很慢，而且质数的乘积唯一，所以可以用质数的乘积做hashing。

fromcollectionsimportdefaultdictclassSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:primes=[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]d=defaultdict(list)forsinstrs:key=1forcins:key*=primes[ord(c)-ord('a')]d[key].append(s)ret=[]forkeyind:ret.append(d[key])returnret

面试最优解：其实字符串直接用作哈希，是很不错的解法，别人帮你做。所以咱们排序下字符串做key就行，也不用占用额外空间。

typedefvector<string>V;classSolution{public:vector<vector<string>>groupAnagrams(vector<string>&strs){vector<V>ans;map<string,int>m;// hash 2 intfor(autos:strs){string s2=s;sort(s2.begin(),s2.end());if(m.count(s2)){intidx=m[s2];ans[idx].push_back(s);}else{ans.push_back(V{s});m[s2]=ans.size()-1;}}returnans;}};