1178. 猜字谜

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 616 阅读时长 ≈ 2 分钟

考点

  • 状态压缩
  • 求二进制数表示的集合的全部子集

题解

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
class Solution {
	private:
		vector<int> ans;
		unordered_map<int, int> wordMap;
	public:
		vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
			for (string &word : words) {
				int hsh = 0;
				for (char &chr : word) {
					hsh |= 1 << (chr - 'a');
				}
				wordMap[hsh]++;
			}
			for (string &puzzle : puzzles) {
				int hsh = 0, cnt = 0;
				for (char &chr : puzzle) {
					hsh |= 1 << (chr - 'a');
				}
				for (int subSet = hsh;; subSet = (subSet - 1) & hsh) {
					if (!subSet) break;
					if (wordMap.count(subSet) && (subSet & (1 << (puzzle[0] - 'a')))) {
						cnt += wordMap[subSet];
					}
				}
				ans.push_back(cnt);
			}
			return ans;
		}
};

时间复杂度：\(O\left( m\cdot w+n\cdot \left( p+2^{bitCount\left( p \right)} \right) \right)\)

其中\(m\)为words数组长度，\(w\)为word的长度且最大为50；\(n\)为puzzles数组长度，\(p\)为puzzle的长度且限定为7

\(bitCount\left( p \right)\)代表十进制整数\(p\)的二进制表达中的1个数；\(2^{bitCount\left( p \right)}\)这一时间复杂度，是求\(p\)二进制表达集合的所有子集

由于\(p\)在这里限定为7，可视为常数；故而时间复杂度也可表达为\(O\left( m\cdot w+n\cdot 2^{bitCount\left( p \right)} \right)\)

空间复杂度：\(O\left( m \right)\)，新增了哈希表

思路

按照传统思路，比较两个字符串的组成至少需要线性时间复杂度；若两个数组内的字符串两两比较，则时间复杂度高达3次方

由于题目说所有字符串只包含小写字母，且需求是对比两个字符串的组成，字符串内部的重复字符并不影响最终结果

所以使用一个32位的int类型变量的低26位，来表达字符串内的字符组成；该int变量也可视作该字符串的哈希值

比如字符串为abd，那么用二进制表达为1011

具体步骤设计如下：

  • 遍历words数组，计算内部所有word字符串的哈希值

    并新建一个哈希表wordMap记录相同哈希值的字符串个数

  • 遍历puzzles数组，计算内部所有puzzle字符串的哈希值的子集

    如果wordMap存在对应子集的记录，且子集包含puzzle的第一个字母

    说明该子集代表的word可以作为当前puzzle的谜底

按照上述步骤即可轻松解题，但需牢记求二进制数表示的集合的全部子集模板，来源于网址：

1
2
3
4
5
// 降序遍历 m 的子集
for (int s = m;; s = (s - 1) & m) {
    // s 是 m 的一个子集
    if (s == 0) break;
}