2273 ~ 移除 anagram 后,找到餐馆数组

土豆炒青椒
·
·
IPFS
相似的代码,相识的套路……

基本信息

  • 题号:2273

  • 题厂:不详(请知情题友告知)

  • 难度系数:低


已知一个包含各种单词的数组 「words」,所有单词均由小写英文字母组成。

在数组「words」中,如果words[i - 1] 和 words[i]互为 anagram,则删除 words[i]。删除完成后返回数组……

什么是Anagram?

就是几个单词有相同字母组成,但字母排列顺序不同……

例如「eat」和「tea」就是一组「同字母异序词」。

根据以上原理,输入 words = ["abba","baba","bbaa","cd","cd"] 返回 ["abba","cd"]

当 i = 1 时,words[i - 1] 为 “abba”,words[i] 为 “baba”,互为 anagram,于是删除 i = 1 的 baba;
当 i = 2 时,words[i - 1] 为 “baba”,words[i] 为 “bbaa”,互为 anagram,于是删除 i = 2 的 bbaa;
当 i = 4 时,words[i - 1] 为 “cd”,words[i] 为 ”cd“,互为 anagram,于是删除 i = 4 的 cd。
遍历完成后,能够返回的只有 ["abba","cd"] 

解题思路

对于只有 26 个小写英文字母的 anagram 检测,我们可以运用 anagram 解题系列的套路模板—— 长度 26 的数组 + ascii 码

本题略有一个陷阱:只有当两个互为 anagram 的单词且 index 连续时,我们才需要删除 index 靠后的单词。也就是说,如果有两个单词,但出现 index 位子不连续,我们也不删除。

例如:["a","b","c","d","a"],i = 0 的 a 与 i = 4 的 a 互为 anagram,但由于 index 不相连,所以不满足删除条件。最后返回结果还是为:["a","b","c","d","a"]。

分析完以上陷阱后,我们发现欲解此题,需要运用的数据结构为 hashmap,key 记录 pattern,value 记录 该 key 最后一次出现的 index


class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        # 创建存储样式的 hashmap 「 pattern : 该样式最后一次出现的 index」
        patterns = {}

        res = []

        for i in range(len(words)):
            # 根据 anagram 题型常用套路,获取该单词的 pattern。
            pattern = [0] * 26
            for w in words[i]:
                code = ord(w) - ord('a')
                pattern[code] += 1

            # ⚠️ list 是不能作为 hashmap 的 key,需要把 list 转换为 tuple
            key = tuple(pattern)
     
            # 略容易犯错的条件:
            # 当 pattern 没有出现在「样式 hashmap」中,或者 pattern 已在「样式 hashmap」但 index 不连续时,当前单词需要被添加进返回数组,同时更新该 pattern 最后一次出现时的 index
            # 只有当 pattern 出现在「样式 hashmap」且 index 连续时,才删除当前单词,更新 index。
            if (key not in patterns) or (key in patterns and (i - 1) > patterns[key]):
                res.append(words[i])
                patterns[key] = i
            elif (i - 1) == patterns[key]:
                patterns[key] = i
            
        return res

Constraints

  • 1 <= words.length <= 100

  • 1 <= words[i].length <= 10

  • words[i] consists of lowercase English letters.

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


测试

  • 当 words 只有 1 个单词时

  • 当 words 有 100 个单词时,测试程序是否有效

  • 当单词只有一个字母时

  • 当单词前后连续互为 anagram 时

  • 当单词前后不为 anagram 时

  • 但单词前后为 anagram 但 index 不连续时

  • ……


Big O

时间复杂度:O(n)

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

空间复杂度: O(n)

  • 引入 hashmap 记录 样式


总结

CC BY-NC-ND 4.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!