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)]1bmtuple(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]]:ddefaultdict(list)forsinstrs:bm[0for_inrange(26)]forcins:bm[ord(c)-ord(a)]1bmtuple(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]ddefaultdict(list)forsinstrs:key1forcins:key*primes[ord(c)-ord(a)]d[key].append(s)ret[]forkeyind:ret.append(d[key])returnret面试最优解其实字符串直接用作哈希是很不错的解法别人帮你做。所以咱们排序下字符串做key就行也不用占用额外空间。typedefvectorstringV;classSolution{public:vectorvectorstringgroupAnagrams(vectorstringstrs){vectorVans;mapstring,intm;// hash 2 intfor(autos:strs){string s2s;sort(s2.begin(),s2.end());if(m.count(s2)){intidxm[s2];ans[idx].push_back(s);}else{ans.push_back(V{s});m[s2]ans.size()-1;}}returnans;}};