西青做网站的公司,高端自适应网站设计,高职示范校建设专题网站,百度快照不更新题目描述 给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的一个新单词。 即将含有相同字符但排列顺序不同的字符串放入同一个组中。 示例 示例 1: 输入: strs [eat, 请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的一个新单词。 即将含有相同字符但排列顺序不同的字符串放入同一个组中。 示例 示例 1: 输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[bat],[nat,tan],[ate,eat,tea]]示例 2: 输入: strs [] 输出: [[]]示例 3: 输入: strs [a] 输出: [[a]] 解题
解法一排序哈希表
思路
如果两个字符串互为字母异位词那么它们含有的字母是一样的只是顺序不同那么可以通过按照相同的排序规则进行排序那么排序结果是一样的。
然后使用排序的结果作为键原来的字符串作为值存放在列表里。
最后以列表的形式返回的所有值即可。
算法复杂度
时间复杂度 O(n * m * log m)其中 n 是输入列表 strs 的长度m 是字符串的最大长度。
对于每个字符串 s我们需要计算其字符的有序版本即 key .join(sorted(s))sorted(s) 的时间复杂度是 O(m log m)其中 m 为字符串 s 的长度。
再加上外部有一个对输入列表 strs 的遍历所以总的时间复杂度是 O(n * m * log m)其中 n 是输入列表 strs 的长度m 是字符串的最大长度。 空间复杂度O(n*m)其中 n 是输入列表 strs 的长度m 是字符串的最大长度。
代码
class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:anagram_groups {}for s in strs:# 将字符串转换为有序的字符串作为哈希表的键key .join(sorted(s))# 如果哈希表中已经有这个键则把当前字符串加入到对应值即组中if key in anagram_groups:anagram_groups[key].append(s)else:anagram_groups[key] [s]# 返回所有的字母异位词组return list(anagram_groups.values())
