此为历史版本和 IPFS 入口查阅区,回到作品页
土豆炒青椒
IPFS 指纹 这是什么

作品指纹

「亚麻」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

CC BY-NC-ND 4.0 授权