题目:https://leetcode-cn.com/problems/group-anagrams
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明:
所有输入均为小写字母。
不考虑答案输出的顺序。
思路:
* 1. 找相同的key, 字符排序重组后作为key,哈希表形式
将排序后的字符串作为哈希表的键,而值则为排序前的字符串
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
if strs is None or len(strs) < 1:
return []
res = {}
ans = []
length = len(strs)
for i in range(length):
s = strs[i]
s_l = list(s)
s_l.sort()
k = ''.join(s_l)
if k not in res:
res[k] = [s]
else:
res[k].append(s)
for k, v in res.items():
ans.append(v)
return ans
* 2. 上述每个元素都需要进行排序,耗时比较多,采用计数法能够避免顺序问题。将字母出现的次数作为哈希表的键。
声明一个长度为 26 的列表,存储每个字符串字符出现的次数,将列表转换为元组,作为哈希表的键。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = collections.defaultdict(list)
for string in strs:
# 声明长度 26 的列表用于计算字符出现的次数
ch_counts = [0] * 26
for ch in string:
# 统计字符串出现次数
ch_counts[ord(ch)-ord('a')] += 1
# 将列表转换为元组,作为键,将当前字符串添加到值中
anagrams[tuple(ch_counts)].append(string)
return [value for value in anagrams.values()]