本文涉及知识点
枚举子集 位运算
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 <= 105
4 <= words[i].length <= 50
1 <= puzzles.length <= 104
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。
状态压缩
状态压缩：如果存在字母ch ，则第(ch-‘a’)位为1。
mMaskCnt[i] 记录包括字母’a’+i的所有words[k]的mask的数量
通过p枚举puzzles
假定p的mask是mask1，则枚举mask所有的自己sub,累加：mMaskCnt[p[0]-‘a’][sub]
注意：
for (int sub = iMask; sub; sub = (sub - 1) & iMask)
这样的时间复杂度是:O(27)
不能for(sub = 0 ;sub < iMask;sub++) 这样的时间复杂度是O(226)
代码
核心代码
class Solution { public: vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) { unordered_map<int, int> mMaskCnt[26]; for (const auto& s : words) { const int iMask = Mask(s); for (int i = 0; i < 26; i++) { if ((1 << i) & iMask) { mMaskCnt[i][iMask]++; } } } vector<int> vRet; for (const auto& s : puzzles) { const int iMask = Mask(s); int iRet = 0; for (int sub = iMask; sub; sub = (sub - 1) & iMask) { if (mMaskCnt[s[0] - 'a'].count(sub)) { iRet += mMaskCnt[s[0] - 'a'][sub]; } } vRet.emplace_back(iRet); } return vRet; } int Mask(const string& s) { int iMask = 0; for (const auto& ch : s) { iMask |= (1 << (ch - 'a')); } return iMask; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<string> words, puzzles; { Solution sln; words = { "apple","pleas","please" }, puzzles = { "aelpsxy","saelpxy","xaelpsy" }; auto res = sln.findNumOfValidWords(words, puzzles); Assert(vector<int>{ 3, 2, 0}, res); } { Solution sln; words = { "apple","pleas","please" }, puzzles = { "aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy" }; auto res = sln.findNumOfValidWords(words, puzzles); Assert(vector<int>{0, 1, 3, 2, 0}, res); } { Solution sln; words = { "aaaa", "asas", "able", "ability", "actt", "actor", "access" }, puzzles = { "aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz" }; auto res = sln.findNumOfValidWords(words, puzzles); Assert(vector<int>{1, 1, 3, 2, 4, 0}, res); } }
