朴素的想法是模拟。即遍历 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 的长度。看下题目的约束条件：
这道题的关键其实就是单词 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 出现的次数，比如：
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)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
