LeetCode 1178.猜字谜

题目描述

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

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

题解

是字谜的要求是：

谜面的第一个字母必须在谜底中存在
谜底的所有字母必须在谜面中存在

整体来说思路还是非常清晰的，注意到上面的条件下，实际上aaaa和a是没区别的，所以正常思路第一步会首先对其进行压缩。
考虑到所有字符都是小写字母，使用 $26$ 位整数即可表示所有情况，int完全足够存储。

注意到谜面固定为长度为 $7$ ，那么实际上每个谜面的谜底是有限的：

固定首先第一位字符必须存在
剩下的字符可能出现也可能不出现，共有 $2^6=64$ 种可能

也即，按照上面的压缩方法重新把谜面编码成整数后，只有 $64$ 种谜底可能。直接统计下每种可能共对应多少个谜底即可。

总体思路：

把所有谜底编码成整数，并统计每个整数对应的个数
把谜面对应的 $64$ 种可能枚举出来，计算相应的谜底个数

很多地方还提到如果word不同的字符多于 $7$ 不插入到map做剪枝。个人觉得如果没有用 CPU 的相关指令来做这个判断的话，指不定在时间上会是个负优化……
在后续的统计部分无论有没有这一步，耗时都是相同的；如果不使用 CPU 直接得到结果，可能循环一下计算出来不同字符的个数再比较下，机器指令指不定比直接无脑插入更多。

最初思路非常清晰往位运算想，基本上看题一分钟后就把整体的位运算代码写好了。
但是一直陷入了误区，花费了大量时间思考如何优化(p | (^w)) & ((1 << 26) - 1) == (1 << 26)
其中p是谜面的编码，w是谜底的编码。潜意识里感觉可以通过预计算，处理出一个所有谜底位运算后的值，只需要把每个谜面与这个值再做一次运算就能直接得到答案。
不过由于涉及了加法和一些魔法数字，一直没有推导出式子。

即使中间注意到了谜面最长为 $7$ ，也只是考虑如何针对这个数做缓存，完全没有往枚举谜面思考。

应该尽早注意到这个原理上应该没法优化，去思考别的办法。并且注意 $7$ 的暗示。毕竟这个数字在题目中太显眼了，每个谜面都是固定为 $7$ ，且字符不同，貌似从来没有见过别的题这么限定过。

代码

go

import (
    "math/bits"
)

func findNumOfValidWords(words []string, puzzles []string) []int {
    m := make(map[int]int)
    for _, word := range words{
        num := 0
        for _, c := range(word) {
            num |= 1<<(c - 'a')
        }
        if bits.OnesCount(uint(num)) <= 7 {
            m[num]++
        }
    }
    res := make([]int, len(puzzles))
    for idx, puzzle := range(puzzles) {
        count := 0
        for i:=0; i<(1<<6); i++ {
            temp := 1 << (puzzle[0] - 'a')
            for j:=0; j<6; j++ {
                temp |= ((i >> j) & 1)<<(puzzle[j+1] - 'a')
            }
            count += m[temp]
        }
        res[idx] = count
    }
    return res
}

python

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def w2n(s):
            num = 0
            for c in s:
                num |= 1<<(ord(c) - ord('a'))
            return num

        m = {}
        for word in words:
            if len(ws := set(word)) <= 7:
                w = w2n(ws)
                m[w] = m.get(w, 0) + 1

        def getRes(puzzle):
            count = 0
            lst = [ord(c) - ord('a') for c in puzzle]
            # 枚举所有可能的谜面
            for i in range(1<<6):
                temp = 1 << lst[0]
                for j in range(6):
                    temp |= (((i>>j) & 1) << lst[j+1])
                count += m.get(temp, 0)
            return count
        return [getRes(puzzle) for puzzle in puzzles]