本文涉及知识点

枚举子集 位运算

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⁵
4 <= words[i].length <= 50
1 <= puzzles.length <= 10⁴
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)

• 1

这样的时间复杂度是:O(2⁷)
不能for(sub = 0 ;sub < iMask;sub++) 这样的时间复杂度是O(2²⁶)

代码

核心代码

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;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33

测试用例

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);
	}
	
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49