【二进制状态压缩】元宵特供——猜灯谜

• 题目背景：
  

/*
LeetCode 1178: Number of Valid Words for Each Puzzle
@Description:
With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:
· word contains the first letter of puzzle.
· For each letter in word, that letter is in puzzle.

For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”;
while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).
Return an array answer, where answer[i] is the number of words
in the given word list words that are valid with respect to the puzzle puzzles[i].

Constraints:
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] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters
*/

• 前言：
  
  • 设Sw为word中出现的字母组成的[不重复]的集合，Sp表示puzzle中出现的字母组成的[不重复]的集合。
    
  • 若存在Sp的某个子集Sp’，Sp’包含puzzle[0]且满足Sp’ == Sw，则word是puzzle的谜底之一
    
  • 初步构想算法流程：
    
    • 计算出每一个word对应的Sw，存放于某一[数据结构]中，以便[快速查找]
      
    • 依次枚举每一个puzzle，计算其对应的集合Sp，并枚举所有满足要求的Sp’，即为谜底的个数
      
• 方法一：二进制状态压缩
  

/
思路：二进制状态压缩
1. 使用一个hash映射表示需要的[数据结构]，key表示一个bit长度为26的二进制数，value表示出现次数
2. 将word做转换方便查找，由于只有小写字母，所以可以用位操作来实现，a - z 对应 0 - 25 bit，转化为mask_word整数
3. 对于puzzle做同样的操作
4. 基于每个puzzle找对应word的转换
· 首先保证puzzle[0]在对应的bit在mask_word中也同样为1
· 枚举mask_puzzle各种为1的情况是否能找到对应的mask_word，找到则加上当映射的数量即可
5. make_puzzle枚举方法： a = (a - 1) & mask，不断去除1位1，直到 a == mask
/
class Solution {
private:
inline int BitCount(int x) {
int res = 0;
while (x > 0) {
res += (x & 1);
x >>= 1;
}
return res;
}
public:
vector findNumOfValidWords(vector& words, vector& puzzles) {
unordered_map table;
for (const string& word : words) {
int mask = 0;
for (char& c : word)
mask |= (1 << (c - ‘a’));
// puzzle.length() = 7，且各字符不同，因此字符不同数目大于7时即可跳过
if (BitCount(mask) <= 7)
table[mask]++;
}
vector res;
for (auto& puzzle : puzzles) {
int mask = 0;
//忽略puzzle[0]
for (int i = 1; i < 7; ++i)
mask |= (1 << (puzzle[i] - ‘a’));
int start = 1 << (puzzle[0] - ‘a’);
int currMask = mask, total = 0, curr = 0;
do {
curr = currMask | start;
if (table.count(curr))
total += table[curr];
currMask = (currMask - 1) & mask;
} while (currMask != mask);
res.emplace_back(total);
}
return res;
}

};