LeetCode Python, Java, C++ > 49. 字母异位词分组 > 已支持 Python, Ruby > GitHub
力扣链接：49. 字母异位词分组，难度等级：中等。
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
约束:
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]仅包含小写字母
相关标签
思路
两个字符串，
bat和atb，用什么方法能最快地知道他们是字母异位词呢？点击查看答案
将每个字符串都按字母表顺序排序，然后比较排过序的两个字符串。相等，就是。
但是排序后，原字符串没有被考虑进来，而结果求的是原字符串的分组。如何解决？
点击查看答案
用元组，即把按字母表顺序排序后的字符串和原字符串放在一个元组里，像这样：
("abt", "bat")。剩下要做的，就是对这个元组数组进行分组了。如何分组最简单？
点击查看答案
用
Map，key是按字母表顺序排过序的字符串，value是原字符串的数组。
👋 站长寄语：我还为你开发了 coder.id - 打造程序员个人IP， 包含作品集、简历和博客等，助您顺利拿到 Offer！
复杂度
时间复杂度
O(N * M * logM)
空间复杂度
O(N)
解释
M = string.length
Python #
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
pairs = [(''.join(sorted(string)), string) for string in strs]
ordered_to_original = defaultdict(list)
for ordered, original in pairs:
ordered_to_original[ordered].append(original)
return list(ordered_to_original.values())
# More concise solution:
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
s_to_list = defaultdict(list)
for s in strs:
s_to_list[
''.join(sorted(s))
].append(s)
print(s_to_list) # defaultdict(<class 'list'>, {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']})
return list(s_to_list.values())
Ruby #
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
result = Hash.new([])
strs.each do |str|
result[str.chars.sort.join] += [str]
end
result.values
end
# Or solution 2: More concise way
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
strs.group_by { |string| string.chars.sort }.values
end
其它语言
欢迎贡献代码到 GitHub repo -> 49. 字母异位词分组。感谢！打造你的开发者个人IP
- 📄 简历 + 作品集 + 博客
- 🌐 支持绑定自定义域名
- ✨ 顶级子域名：
https://yourname.coder.id