Leetcode Link: 49. 字母异位词分组 - 力扣（LeetCode）
题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
本质上就是对给定的字符串数组进行分组
解法一
思路：暴力
- 每次取 strs 里的第一个字符串（建议pop(0)）
- 对其进行计数：
Counter() - 遍历 strs，找计数结果一样的，添加到当前组
- 将当前组添加到结果中
超时
题解：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = []
while(len(strs)>0):
new = [strs.pop(0)] # 当前分组
cur = Counter(new[0]) # 计数
j = 0
while(j < len(strs)): # 逐个遍历
tmp_counter = Counter(strs[j])
if tmp_counter == cur:
# 有就弹出，并添加到当前分组
new.append(strs[j])
strs.pop(j)
else:
j += 1
res.append(new)
return res解法二
思路： 分析上述问题超时的原因：
- 可能是 pop 的次数太多，因为 list 的 pop 操作代价比较大，因此我们考虑避免 pop 操作
- 我们遍历 strs 的次数过多，导致浪费
改进：
- 创建 res 和 res_counter, 前者用来保存结果，后者用来保存 res 中对应位置（对应组）的 counter
- 只遍历一次strs，取出一个s，制作s_counter, 遍历res_counter，找不到则按照新来的处理，找到了则添加到对应的res分组中去
题解：依然超时…
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = []
res_counter = []
for i, s in enumerate(strs):
s_counter = Counter(s) # 取出当前的s
flag = 0
for j, tar_counter in enumerate(res_counter):
if s_counter == tar_counter:
res[j].append(s)
flag = 1
break # 找到了就不用看了
if flag == 0:
res.append([s])
res_counter.append(s_counter)
return res解法三
思路：可能是遍历的 res_counter 次数太多
在这种思路下，我们无论如何都要在在 res_counter 中看一下，因此思考如何减少“看”的次数
由于这是字母，counter 可以用一个 [1,26] 的列表来制作，进而避免使用Counter()，对应位置保存的是对应字母的出现顺序，然后多添加一位（27 位），用来保存这个 counter 对应的字符串的长度，并利用长度进行分组和排序，减少”看”的次数
这样就会出现另一个问题，利用长度分组了，怎么找到对应长度分组里的某一个计数对应 res 哪一个字符串？
可以再补充一个位置（第 28 位），用来保存对应 res 的位置（类似解法二中 res_counter 和 res 的关系是一一对应的，这里 res_counter 和 res 关系由 res_counter 中第 28 位 (res_counter[27] 指定))
题解：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res_counter = [[] for _ in range(100)] # 保存对应长度的counter，每个元素是一个列表
res = []
for i, s in enumerate(strs):
# [0~25] 字母计数， [26] 长度, [27] 对应res的索引，在主函数里写
s_counter = self.get_counter(s)
flag = 0
cur_len = s_counter[26]
for j, tar_counter in enumerate(res_counter[cur_len]): # 只在对应长度的组里去找
# 看看counter是不是相等，只考虑前26位
if s_counter[:26] == tar_counter[:26]:
res[tar_counter[27]].append(s)
flag = 1
break
# 若没有找到目标，则需要执行三步
# 1. 结果res中 s 独立为新的一组
# 2. 将res_counter中的27位指定为对应res的位置
# 3. 在对应长度的分组中添加s_counter.
if flag == 0:
res.append([s])
s_counter[27] = len(res)-1
res_counter[cur_len].append(s_counter)
return res
def get_counter(self, s):
counter = [0]*28 # [0~25] 字母计数， [26] 长度, [27] 对应res的索引，在主函数里写
for c in s:
idx = ord(c) - ord('a')
counter[idx] += 1
counter[26] = len(s)
return counter解法四
思路
主要是 dict.get() 函数的理解
dict.get(key, default=None)key— 字典中要查找的键。default— 如果指定键的值不存在时，返回该默认值。
还有一点要注意：因为字典的键，必须是不可变类型，所以用 tuple。
题解
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dict = {}
for item in strs:
key = tuple(sorted(item))
# a1 = [123] a2 = [234] a1+a2 = [123, 234]
dict[key] = dict.get(key, []) + [item]
return list(dict.values())Attention
- 两个列表相加 = append
- 同理可以直接操作
dict.keys()