「亚麻」49 ～ 同字母异序词 分组

基本信息

• 题号：49

• 题厂：亚麻

• 难度系数：中

已知一个包含各种单词的数组。如果某单词互为 anagrams（同字母异序词），则分为一组并返回

什么是Anagram？

就是几个单词又相同字母组成，但字母排列顺序不同……例如「eat」和「tea」就是一组「同字母异序词」。

根据以上原理，输入 strs = ["eat","tea","tan","ate","nat","bat"] 返回 [["bat"],["nat","tan"],["ate","eat","tea"]]

解题思路

理解题目要求后，要判断单词之间是否互为「anagram」，需要引入数据结构 set。将已出现的 set 划归为一组即可。

而在存贮循环遍历过程中出现过的 set 组合，首先想到需要使用数据结构 HashMap。key 为 set 样式，value 为符合该样式的单词。

对于本题，题目已知单词均为 26 个小写字母，所以我们可以通过 ascii 码和长度为 26 的数组记录 set 样式。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # map 样式 「样式」- 所属单词
        patterns = {}
        
        # 遍历输入单词，根据对应 ascii 码获取该单词样式。如果样式已出现在 patterns 记录中，则对应添加；如果还没有，则创建新样式。
        # ⚠️数组不能作为 hashmap 的 key，需要把 数组转换为 tuple
        for s in strs:
            pattern = [0] * 26
            for c in s:
                pattern[ord(c) - 97] += 1

            pattern_key = tuple(pattern)

            if pattern_key in patterns:
                patterns[pattern_key].append(s)
            else:
                patterns[pattern_key] = [s]
        
        # 遍历分析完毕后，将分组好的单词们放进返回值 res
        res = []
        for v in patterns.values():
            res.append(v)

        return res

Constraints

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] consists of lowercase English letters.

做题前要和考官讨论单词中可能出现的字符范围。本题提示只会出现小写英文字母，所以 「ascii + 数组」 解法可行。

测试

• 当单词包含多个重复字母时

• 当单词包含不同字母顺序不同时

• 当输入单词长度为 0 或 100 的 edge case 时

• ……

Big O

时间复杂度：O（n）

循环一遍，复杂度为 n，遍历单词字母，最长为 100 个字母，最差复杂度为 O（100n），化简后还是 O（n）

空间复杂度： O（n）

• 引入 hashmap 记录 样式

总结

• 题号靠前，属于 anagram 类别经典题

• 本题解题思路容易想到，但数组不能作为 hashmap 的key 存储容易犯错。

• 「acsii 码 + 数组」是处理字符串的常见技巧。

• 同类套路相似题型：2273，242