位運算基礎(chǔ)

• set bit: mask |= (1 << puzzle[i])
• submask : `submask |= (submask - 1) & mask

位置掩碼

https://leetcode-cn.com/problems/subsets/
先來看78題

78. 子集
    給你一個整數(shù)數(shù)組nums ，數(shù)組中的元素互不相同。返回該數(shù)組所有可能的子集（冪集）。
    解集不能包含重復(fù)的子集。你可以按任意順序返回解集。

思路

遍歷位置掩碼即可得到子集

字符集掩碼

https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/
今日每日一題

1178. 猜字謎
      外國友人仿照中國字謎設(shè)計了一個英文版猜字謎小游戲，請你來猜猜看吧。
      字謎的迷面 puzzle 按字符串形式給出，如果一個單詞 word 符合下面兩個條件，那么它就可以算作謎底：
      單詞 word 中包含謎面 puzzle 的第一個字母。
      單詞 word 中的每一個字母都可以在謎面 puzzle 中找到。
      例如，如果字謎的謎面是 "abcdefg"，那么可以作為謎底的單詞有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 沒有出現(xiàn)在謎面中）。
      返回一個答案數(shù)組 answer，數(shù)組中的每個元素 answer[i] 是在給出的單詞列表 words 中可以作為字謎迷面 puzzles[i] 所對應(yīng)的謎底的單詞數(shù)目。

由于puzzle和word都是小寫英文字符串，所以這是一個僅有26位的字符集掩碼問題。

第一步：狀態(tài)壓縮

本質(zhì)上來說雖然word和puzzle里的各字符出現(xiàn)次數(shù)和順序，但判定的依據(jù)都是出現(xiàn)的字符的集合。
故可以壓縮為字符掩碼。

第二步：計算puzzle的子集

注意：計算的是不包括頭部的子掩碼集合

由于頭部必有，所以只需要計算剩余部分的子掩碼集合

for(int i = 1; i < 7;   i)
  mask |= (1 << puzzle[i]);  //set bit

計算子掩碼集合

計算子集最終要轉(zhuǎn)變?yōu)樽友诖a，故直接計算子掩碼也可。
關(guān)鍵代碼:

submask = mask;
do{
  submask = (submask - 1) & mask;
}while(submask != mask);

這里submask = (submask - 1) & mask 之所以能夠迭代submask而不重不漏，是因為submask的位模式是能夠與mask按位與后產(chǎn)生submask的最小二進(jìn)制數(shù)（聽起來像句廢話），所以再減去1就能得到與mask相與得到 更小的submask 的位模式。

兩題的區(qū)別

字符集掩碼的全集的位模式由于并不是所有位都占了，所以并不能用位置掩碼（全集的位模式是所有位置都為1）那一套來計算。