Scott's Blog

学则不固, 知则不惑

0%

算法题: 字母异位词分组

📌 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。Leetcode

思考

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。

使用题目"有效的字母异位词"思路判断异位词。

对数组中的每一个元素进行组合执行上面的判断, 需要将所有的异位词放到一个数组,所以需要构建另外一个数组。

如果找到了一个新的形式,需要将新的放到这个数组,比对的对象可以是第一个,因为所有异位词之间应该都是相等的关系, 那么可以使用第一个遇到的词语作为键和值,后续找到的新的放到值中。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def groupAnagrams(strs: list):
angram_dict = {}

for i in range(len(strs)):
for j in range(i+1, len(strs)):
is_angram = isAnagramCounter(strs[i], strs[j])
if is_angram:
if strs[i] in angram_dict:
angram_dict[strs[i]].append(strs[j])
elif strs[i] in angram_dict.values():
continue
else:
angram_dict[strs[i]] = []
angram_dict[strs[i]].append(strs[j])

return angram_dict

groupAnagrams(strs)

上面的双重循环增加了很多复杂度,可以直接借鉴排序的优秀解法,其中 tuple(sorted(w)) 也可以换成 ''.join(sorted(w))。

1
2
3
4
5
6
7
8
9
10
11
# 记住 d.get(key, []) + [w]
strs = ["eat","tea","tan","ate","nat","bat"]

def groupAnagrams(strs):
d = {}
for w in sorted(strs):
key = tuple(sorted(w))
d[key] = d.get(key, []) + [w]
return d.values()

groupAnagrams(strs)