LeetCode刷题实战49：字母异位词分组
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 字母异位词分组，我们先来看题面：
https://leetcode-cn.com/problems/group-anagrams/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
题意
样例
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
解题
https://www.cnblogs.com/techflow/p/12693828.html
暴力
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
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
hash
def hash(dict):
ret = 0
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
，单个b的hash值也很好算，是23。请问23个a的hash值是多少？算一下就知道，也是23。因为虽然我们用的幂不同，但是它们的底数是一样的，我们可以用前面的系数来弥补指数的差。这种不同的对象hash结果一样的情况叫做hash碰撞，这种是不符合我们预期的。但是可以肯定的是，大多数情况下hash碰撞几乎是不可避免的。因为我们hash的目的就是为了用一个简单的数字或者字符串代替原本复杂庞大的数据，就好像拍照一样，两个不同的人，也可能拍出来看起来很像。
from collections import defaultdict
import math
class Solution:
def splitStr(self, s):
hashtable = [0 for _ in range(30)]
ret = 0
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
上期推文：
评论