第六章 - 高频考题(困难)
1178. 猜字谜

题目地址(1178. 猜字谜)

题目描述

1
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。
2
3
字谜的迷面 puzzle 按字符串形式给出,如果一个单词 word 符合下面两个条件,那么它就可以算作谜底:
4
5
单词 word 中包含谜面 puzzle 的第一个字母。
6
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
7
例如,如果字谜的谜面是 "abcdefg",那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage";而 "beefed"(不含字母 "a")以及 "based"(其中的 "s" 没有出现在谜面中)。
8
9
返回一个答案数组 answer,数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
10
11
12
13
示例:
14
15
输入:
16
words = ["aaaa","asas","able","ability","actt","actor","access"],
17
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
18
输出:[1,1,3,2,4,0]
19
解释:
20
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
21
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
22
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
23
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
24
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
25
没有单词可以作为 "gaswxyz" 的谜底,因为列表中的单词都不含字母 'g'。
26
27
28
29
30
提示:
31
32
1 <= words.length <= 10^5
33
4 <= words[i].length <= 50
34
1 <= puzzles.length <= 10^4
35
puzzles[i].length == 7
36
words[i][j], puzzles[i][j] 都是小写英文字母。
37
每个 puzzles[i] 所包含的字符都不重复。
Copied!

前置知识

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

公司

  • 暂无

位运算

思路

朴素的想法是模拟。即遍历 puzzles 和 words 的所有组合,并判断是否满足条件,如果满足则计数器+1,最后返回计数器的值。
暴力法代码:
1
class Solution:
2
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
3
s_word = [set(word) for word in words]
4
ans = []
5
for puzzle in puzzles:
6
cnt = 0
7
for word in s_word:
8
if puzzle[0] not in word:
9
continue
10
flag = False
11
for c in word:
12
if c not in puzzle:
13
flag = True
14
break
15
if not flag:
16
cnt += 1
17
ans.append(cnt)
18
return ans
Copied!
由于这种做法需要遍历 puzzles 和 words 的所有组合,因此时间复杂不低于是 $O(m * n)$,其中 m 和 n 分别为 words 和 puzzles 的长度。看下题目的约束条件:
1
1 <= words.length <= 10^5
2
1 <= puzzles.length <= 10^4
Copied!
可知道 m * n 最大可以是 $10 ^ 9$ ,这显然是无法接受的。
lucifer 小提示:小于等于 10 ^ 7 才可以哦
注意到题目的约束条件:
1
puzzles[i].length == 7
Copied!
基本可以锁定为是状态压缩。力扣相关的题目很多,基本都是有一个约束条件的数据范围很小(比如 20 以内)。我们要做的通常就是给这个小的变量做状态压缩
这道题的关键其实就是单词 word 中的每一个字母都可以在谜面 puzzle 中找到,所有的重复计算都是基于此产生的。这句话的含义其实就是word 中字符组成的集合是 puzzle 中组成的集合的子集
基于上面两条重要信息,我们可以初步锁定算法为:
  • 用二进制表示 puzzle
  • 枚举 puzzle 的所有子集(二进制子集枚举)
  • 判断所有子集 j 是否在 words 中出现过。如果出现过,则将计数器累加出现的次数。这提示我们同样将 word 使用二进制进行存储。虽然 words[i] 的长度范围比较大([4,50]),但我们关心的其实是去重的子集。注意到 words[i] 的取值范围是小写字符,因此这个范围不大于 26,使用 int 存储完全够了。
枚举二进制子集是一个常见的操作,竞赛中也不时出现,大家可以阅读相关内容,具体原理不再展开。

关键点

  • 枚举子集算法

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
3
counts = collections.defaultdict(int)
4
ans = [0] * len(puzzles)
5
for word in words:
6
bit = 0 # bit 是 word 的二进制表示
7
for c in word:
8
bit |= 1 << ord(c) - ord("a")
9
counts[bit] += 1
10
for i, puzzle in enumerate(puzzles):
11
bit = 0 # bit 是 puzzle 的二进制表示
12
for c in puzzle:
13
bit |= 1 << ord(c) - ord("a")
14
j = bit # j 是 bit 的子集
15
# 倒序枚举 bit 的子集 j
16
while j:
17
# 单词 word 需要包含谜面的第一个字母
18
if 1 << ord(puzzle[0]) - ord("a") & j:
19
ans[i] += counts[j]
20
j = bit & (j - 1)
21
return ans
Copied!
复杂度分析
令 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 出现的次数,比如:
1
{
2
"abc": 3
3
}
Copied!
这就可以仅判断一次而不是多次了,这就减少了判断。而这对于我们求的答案来说是等价的。除此之外,word 中一个字符出现几次对我们来说是一样的。比如 words: ["abc", "aaaaabbbc"] 可以看成是 ["abc", "abc"] 这对于我们求的答案来说是等价的
因此我们可以将其进行一次排序并去重。同理,我们需要对 puzzle 进行排序并去重。而由于题目规定了 puzzle 本身不含重复字符,因此只对 puzzle 进行排序也是可以的。
这种做法同样需要枚举 puzzle 的子集。伪代码:
1
def get_subset(puzzle, pos):
2
# ...
3
get_subset(next_with_puzzle_pos , pos + 1) # 选 pos
4
get_subset(next_without_puzzle_pos, pos + 1) # 不选 pos
5
# ...
Copied!
由于第一个必选,因此上面的逻辑需要做一些微调,具体看下方代码区。

关键点

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

代码

  • 语言支持:Python3
Python3 Code:
1
class TrieNode:
2
def __init__(self):
3
self.count = 0
4
self.children = {}
5
6
7
class Trie:
8
def __init__(self):
9
self.root = TrieNode()
10
11
def insert(self, word):
12
cur = self.root
13
for c in word:
14
if c not in cur.children:
15
cur.children[c] = TrieNode()
16
cur = cur.children[c]
17
cur.count += 1
18
19
20
class Solution:
21
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
22
trie = Trie()
23
for word in words:
24
trie.insert(sorted(set(word)))
25
26
def get_count(first_letter, cur, i, puzzle):
27
if i == len(puzzle):
28
return cur.count
29
if not cur:
30
return 0
31
ans = 0
32
# 这个判断成立的条件是 puzzle 中不存在重复的字符, 这恰好就是题目的限制条件
33
if puzzle[i] != first_letter:
34
ans += get_count(first_letter, cur, i + 1, puzzle)
35
if puzzle[i] in cur.children:
36
ans += get_count(first_letter, cur.children[puzzle[i]], i + 1, puzzle)
37
return ans
Copied!
复杂度分析
令 m 为 words 长度,w 为 word 的平均长度。n 为 puzzles 的长度,p 为 puzzle 的平均长度。
  • 时间复杂度:$O(mw + n2^p)$
  • 空间复杂度:$O(m*w + p)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。