Leetcode 1178:猜字谜(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1178:猜字谜(超详细的解法!!!)

in leetcode with 0 comment

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

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

返回一个答案数组 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'。

提示:

解题思路

首先不难想到暴力解法,就是将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

我们在Leetcode 1177:构建回文串检测(超详细的解法!!!)中使用一个int变量存储26个字母,那么这个问题也可以使用这种策略。另外求子集,我们可以通过之前Leetcode 78:子集(最详细的解法!!!)迭代的策略来处理。

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

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

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses