LeetCode 1178. 猜字谜

Question

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：

输入：
words = ["aaaa","asas","able","ability","actt","actor","access"],
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

提示：

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。

前置知识

• 枚举子集
• 位运算
• 前缀树

公司

• 暂无

位运算

思路

朴素的想法是模拟。即遍历 puzzles 和 words 的所有组合，并判断是否满足条件，如果满足则计数器+1，最后返回计数器的值。

暴力法代码：

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        s_word = [set(word) for word in words]
        ans = []
        for puzzle in puzzles:
            cnt = 0
            for word in s_word:
                if puzzle[0] not in word:
                    continue
                flag = False
                for c in word:
                    if c not in puzzle:
                        flag = True
                        break
                if not flag:
                    cnt += 1
            ans.append(cnt)
        return ans

由于这种做法需要遍历 puzzles 和 words 的所有组合，因此时间复杂不低于是 $O(m * n)$，其中 m 和 n 分别为 words 和 puzzles 的长度。看下题目的约束条件：

1 <= words.length <= 10^5
1 <= puzzles.length <= 10^4

可知道 m * n 最大可以是 $10 ^ 9$ ，这显然是无法接受的。

lucifer 小提示：小于等于 10 ^ 7 才可以哦

注意到题目的约束条件：

puzzles[i].length == 7

基本可以锁定为是状态压缩。力扣相关的题目很多，基本都是有一个约束条件的数据范围很小（比如 20 以内）。我们要做的通常就是给这个小的变量做状态压缩。

这道题的关键其实就是单词 word 中的每一个字母都可以在谜面 puzzle 中找到，所有的重复计算都是基于此产生的。这句话的含义其实就是word 中字符组成的集合是 puzzle 中组成的集合的子集。

基于上面两条重要信息，我们可以初步锁定算法为：

• 用二进制表示 puzzle
• 枚举 puzzle 的所有子集（二进制子集枚举）
• 判断所有子集 j 是否在 words 中出现过。如果出现过，则将计数器累加出现的次数。这提示我们同样将 word 使用二进制进行存储。虽然 words[i] 的长度范围比较大（[4,50]），但我们关心的其实是去重的子集。注意到 words[i] 的取值范围是小写字符，因此这个范围不大于 26，使用 int 存储完全够了。

枚举二进制子集是一个常见的操作，竞赛中也不时出现，大家可以阅读相关内容，具体原理不再展开。

关键点

• 枚举子集算法

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        counts = collections.defaultdict(int)
        ans = [0] * len(puzzles)
        for word in words:
            bit = 0 # bit 是 word 的二进制表示
            for c in word:
                bit |= 1 << ord(c) - ord("a")
            counts[bit] += 1
        for i, puzzle in enumerate(puzzles):
            bit = 0 # bit 是 puzzle 的二进制表示
            for c in puzzle:
                bit |= 1 << ord(c) - ord("a")
            j = bit # j 是 bit 的子集
            # 倒序枚举 bit 的子集 j
            while j:
                # 单词 word 需要包含谜面的第一个字母
                if 1 << ord(puzzle[0]) - ord("a") & j:
                    ans[i] += counts[j]
                j = bit & (j - 1)
        return ans

复杂度分析

令 m 为 words 长度，w 为 word 的平均长度。n 为 puzzles 的长度，p 为 puzzle 的平均长度。

• 时间复杂度：$O(mw + n2^p)$
• 空间复杂度：$O(m)$

字典树

思路

看了官方的解答还提供了字典树的解法。于是我也用字典树实现了一遍。

之所以可以使用字典树求解是因为我们只关心：

• word 是否是 puzzle 的子集
• 如果是，则关心 word 出现的次数

但由于类似：words: ["abc", "acb", "bac"] 等的存在，使得判断的时间大大增加，如果进行一次排序，此时 words 为：["abc", "abc", "abc"]，而如果统计排序后相同 word 出现的次数，比如：

{
    "abc": 3
}

这就可以仅判断一次而不是多次了，这就减少了判断。而这对于我们求的答案来说是等价的。除此之外，word 中一个字符出现几次对我们来说是一样的。比如 words: ["abc", "aaaaabbbc"] 可以看成是 ["abc", "abc"] 这对于我们求的答案来说是等价的。

因此我们可以将其进行一次排序并去重。同理，我们需要对 puzzle 进行排序并去重。而由于题目规定了 puzzle 本身不含重复字符，因此只对 puzzle 进行排序也是可以的。

这种做法同样需要枚举 puzzle 的子集。伪代码：

def get_subset(puzzle, pos):
  # ...
  get_subset(next_with_puzzle_pos , pos + 1) # 选 pos
  get_subset(next_without_puzzle_pos, pos + 1) # 不选 pos
  # ...

由于第一个必选，因此上面的逻辑需要做一些微调，具体看下方代码区。

关键点

• 字典树的基本用法
• 递归枚举子集

代码

• 语言支持：Python3

Python3 Code:

 class TrieNode:
    def __init__(self):
        self.count = 0
        self.children = {}


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.count += 1


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = Trie()
        for word in words:
            trie.insert(sorted(set(word)))

        def get_count(first_letter, cur, i, puzzle):
            if i == len(puzzle):
                return cur.count
            if not cur:
                return 0
            ans = 0
            # 这个判断成立的条件是 puzzle 中不存在重复的字符， 这恰好就是题目的限制条件
            if puzzle[i] != first_letter:
                ans += get_count(first_letter, cur, i + 1, puzzle)
            if puzzle[i] in cur.children:
                ans += get_count(first_letter, cur.children[puzzle[i]], i + 1, puzzle)
            return ans

复杂度分析

令 m 为 words 长度，w 为 word 的平均长度。n 为 puzzles 的长度，p 为 puzzle 的平均长度。

• 时间复杂度：$O(mw + n2^p)$
• 空间复杂度：$O(m*w + p)$