<h1 id="leetcode-1178">LeetCode 1178.猜字谜</h1>
<h2 id="heading">题目描述</h2>
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 <code>puzzle</code> 按字符串形式给出，如果一个单词 <code>word</code> 符合下面两个条件，那么它就可以算作谜底：
单词 <code>word</code> 中包含谜面 <code>puzzle</code> 的第一个字母。 
单词 <code>word</code> 中的每一个字母都可以在谜面 <code>puzzle</code> 中找到。 
例如，如果字谜的谜面是 &quot;abcdefg&quot;，那么可以作为谜底的单词有 &quot;faced&quot;, &quot;cabbage&quot;, 和 &quot;baggage&quot;；而 &quot;beefed&quot;（不含字母 &quot;a&quot;）以及 &quot;based&quot;（其中的 &quot;s&quot; 没有出现在谜面中）。 
返回一个答案数组 <code>answer</code>，数组中的每个元素 <code>answer[i]</code> 是在给出的单词列表 <code>words</code> 中可以作为字谜迷面 <code>puzzles[i]</code> 所对应的谜底的单词数目。
 
示例：
输入： 
<code>words = [&quot;aaaa&quot;,&quot;asas&quot;,&quot;able&quot;,&quot;ability&quot;,&quot;actt&quot;,&quot;actor&quot;,&quot;access&quot;]</code> 
<code>puzzles = [&quot;aboveyz&quot;,&quot;abrodyz&quot;,&quot;abslute&quot;,&quot;absoryz&quot;,&quot;actresz&quot;,&quot;gaswxyz&quot;]</code> 
输出：<code>[1,1,3,2,4,0]</code> 
解释：
<pre style="background-color:#fff">1 个单词可以作为 &#34;aboveyz&#34; 的谜底 : &#34;aaaa&#34; 
1 个单词可以作为 &#34;abrodyz&#34; 的谜底 : &#34;aaaa&#34;
3 个单词可以作为 &#34;abslute&#34; 的谜底 : &#34;aaaa&#34;, &#34;asas&#34;, &#34;able&#34;
2 个单词可以作为 &#34;absoryz&#34; 的谜底 : &#34;aaaa&#34;, &#34;asas&#34;
4 个单词可以作为 &#34;actresz&#34; 的谜底 : &#34;aaaa&#34;, &#34;asas&#34;, &#34;actt&#34;, &#34;access&#34;
没有单词可以作为 &#34;gaswxyz&#34; 的谜底，因为列表中的单词都不含字母 &#39;g&#39;。
</pre>提示：
<pre style="background-color:#fff">1 &lt;= words.length &lt;= 10^5
4 &lt;= words[i].length &lt;= 50
1 &lt;= puzzles.length &lt;= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。
</pre><h2 id="heading-1">题解</h2>
是字谜的要求是：
<ol>
<li>谜面的第一个字母必须在谜底中存在</li>
<li>谜底的所有字母必须在谜面中存在</li>
</ol>
整体来说思路还是非常清晰的，注意到上面的条件下，实际上<code>aaaa</code>和<code>a</code>是没区别的，所以正常思路第一步会首先对其进行压缩。 
考虑到所有字符都是小写字母，使用 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>26</mn></mrow><annotation encoding="application/x-tex">26</annotation></semantics></math>26 位整数即可表示所有情况，<code>int</code>完全足够存储。
注意到谜面固定为长度为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math>7，那么实际上每个谜面的谜底是有限的：
<ol>
<li>固定首先第一位字符必须存在</li>
<li>剩下的字符可能出现也可能不出现，共有 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mn>6</mn></msup><mo>=</mo><mn>64</mn></mrow><annotation encoding="application/x-tex">2^6=64</annotation></semantics></math>26=64 种可能</li>
</ol>
也即，按照上面的压缩方法重新把谜面编码成整数后，只有<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>64</mn></mrow><annotation encoding="application/x-tex">64</annotation></semantics></math>64种谜底可能。直接统计下每种可能共对应多少个谜底即可。
总体思路：
<ol>
<li>把所有谜底编码成整数，并统计每个整数对应的个数</li>
<li>把谜面对应的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>64</mn></mrow><annotation encoding="application/x-tex">64</annotation></semantics></math>64 种可能枚举出来，计算相应的谜底个数</li>
</ol>
很多地方还提到如果<code>word</code>不同的字符多于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math>7 不插入到<code>map</code>做剪枝。个人觉得如果没有用 CPU 的相关指令来做这个判断的话，指不定在时间上会是个负优化…… 
在后续的统计部分无论有没有这一步，耗时都是相同的；如果不使用 CPU 直接得到结果，可能循环一下计算出来不同字符的个数再比较下，机器指令指不定比直接无脑插入更多。
<hr>
最初思路非常清晰往位运算想，基本上看题一分钟后就把整体的位运算代码写好了。 
但是一直陷入了误区，花费了大量时间思考如何优化<code>(p | (^w)) &amp; ((1 &lt;&lt; 26) - 1) == (1 &lt;&lt; 26)</code> 
其中<code>p</code>是谜面的编码，<code>w</code>是谜底的编码。潜意识里感觉可以通过预计算，处理出一个所有谜底位运算后的值，只需要把每个谜面与这个值再做一次运算就能直接得到答案。 
不过由于涉及了加法和一些魔法数字，一直没有推导出式子。
即使中间注意到了谜面最长为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math>7，也只是考虑如何针对这个数做缓存，完全没有往枚举谜面思考。
应该尽早注意到这个原理上应该没法优化，去思考别的办法。并且注意 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math>7 的暗示。毕竟这个数字在题目中太显眼了，每个谜面都是固定为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math>7，且字符不同，貌似从来没有见过别的题这么限定过。
<h2 id="heading-2">代码</h2>
<h3 id="go">go</h3>
<pre style="background-color:#fff">import (
 &#34;math/bits&#34;
)

func findNumOfValidWords(words []string, puzzles []string) []int {
 m := make(map[int]int)
 for _, word := range words{
 num := 0
 for _, c := range(word) {
 num |= 1&lt;&lt;(c - &#39;a&#39;)
 }
 if bits.OnesCount(uint(num)) &lt;= 7 {
 m[num]++
 }
 }
 res := make([]int, len(puzzles))
 for idx, puzzle := range(puzzles) {
 count := 0
 for i:=0; i&lt;(1&lt;&lt;6); i++ {
 temp := 1 &lt;&lt; (puzzle[0] - &#39;a&#39;)
 for j:=0; j&lt;6; j++ {
 temp |= ((i &gt;&gt; j) &amp; 1)&lt;&lt;(puzzle[j+1] - &#39;a&#39;)
 }
 count += m[temp]
 }
 res[idx] = count
 }
 return res
}
</pre><h3 id="python">python</h3>
<pre style="background-color:#fff">class Solution:
 def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -&gt; List[int]:
 def w2n(s):
 num = 0
 for c in s:
 num |= 1&lt;&lt;(ord(c) - ord(&#39;a&#39;))
 return num

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

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