leetcode每日一题：49. 字母异位词分组
leetcode每日一题：49. 字母异位词分组
用户3578099
发布于 2020-12-30 11:29:07
发布于 2020-12-30 11:29:07
题目：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()]本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读