本文共 2902 字，大约阅读时间需要 9 分钟。

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

字谜的迷面 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] 所包含的字符都不重复。

解题思路

首先不难想到暴力解法，就是将words里面的所有单词存储为set，假设为set(word)。接着遍历所有的puzzles，判断我们的每个puzzle是不是首字母在word中，并且set(word)是不是set(puzzle)的子集。

class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        words, res = [set(word) for word in words], []        for puzzle in puzzles:            cnt = 0            for word in words:                ps = set(puzzle)                if puzzle[0] in word and (ps | word) == ps:                    cnt += 1            res.append(cnt)        return res

这里使用了trick，我们通过集合的|运算求取两个集合的并集，如果这个并且包含在set(puzzle)中，那么说明set(word)是set(puzzle)的子集。显然这种做法超时了。

我们可以这样去优化，首先通过字典可以统计所有set(word)出现的次数，使用cnt表示。然后对puzzle，我们列举它的所有子集，我们每个子集在cnt中的次数累加，最后得到的结果就是我们需要的。

class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        cnt = collections.Counter(frozenset(w) for w in words)        res = []        for p in puzzles:            cur = 0            for k in range(7):                for c in itertools.combinations(p[1:], k):                    cur += cnt[frozenset(tuple(p[0]) + c)]            res.append(cur)        return res

注意我们这里使用的frozenset，因为set是可变对象不能hash。

我们在中使用一个int变量存储26个字母，那么这个问题也可以使用这种策略。另外求子集，我们可以通过之前迭代的策略来处理。

class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        count = collections.Counter()        for w in words:            if len(set(w)) > 7:                 continue            m = 0            for c in w:                m |= 1 << (ord(c) - 97)            count[m] += 1                    res = []        for p in puzzles:            subset = [1 << (ord(p[0]) - 97)]            for c in p[1:]:                subset += [m | 1 << (ord(c) - 97) for m in subset]            res.append(sum(count[m] for m in subset))        return res

reference:

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/discuss/371864/Python-Find-all-Sub-Puzzles

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/100569179 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！