【2.26】LeetCode每日一题·猜字谜

2021年02月26日 13时20分

标签： LeetCode 二进制哈希表

## 题目描述
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 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^5
	4 <= words[i].length <= 50
	1 <= puzzles.length <= 10^4
	puzzles[i].length == 7
	words[i][j], puzzles[i][j] 都是小写英文字母。
	每个 puzzles[i] 所包含的字符都不重复。
	
#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/ "题目链接")

## 解题思路
首先注意理解题意。`单词word中的每一个字母都可以在谜面puzzle中找到`实际上表明两点：

1. 单词内部的顺序和各个字母出现的次数都是无关紧要的（**相当于可以将单词看成一个集合**）。同样地，也可以**将谜面看成一个集合**。
2. 将单词和谜面看成集合后，结合第一个条件“单词 word 中包含谜面 puzzle 的第一个字母”。这两句话可以转化为：
	`word`是`puzzle`的谜底 当且仅当 **`word`表示的集合是`puzzle`表示的集合的一个子集且该子集包含puzzle的首字母**。

那么最后的答案求解算法步骤可以表示为：

1. 将每个单词转变为集合形式，求出各个集合所代表的单词个数。
2. 遍历`puzzles`数组中的每一个谜面`puzzle`，求其代表集合的所有包含首字母的子集。所有这些子集代表的单词个数的总和即为该谜面`puzzle`的谜底数。

注意到，`puzzle`包含的字母数小于7，因此「求其代表集合的所有包含首字母的子集」操作在最坏情况下需要执行$$2^6$$次。此外，由于需要遍历`puzzles`中的每一个`puzzle`，因此第`2`步的总时间复杂度为$$O(n|p|+n2^{|p-1|}) = O(n2^{|p|})$$，其中$$n$$为`puzzles`的长度，$$|p|$$为谜面的最大长度。
而第`1`步需要遍历所有单词和每个单词的所有字母，时间复杂度为$$O(m|w|)$$，其中$$m$$为数组`words`的长度，$$|w|$$为`word`的最大长度。
因此，总时间复杂度$$O(m|w|+ n2^{|p|})$$，在可以接受的范围之内。

为了实现上述算法，对应地，我们需要解决两个问题：
1. **如何表示这个集合？**
	由于单词和谜面中只包含小写英文字母，自然想到使用一个长度为26的二进制数来表示单词和谜面。如果字母`X (X为'a'到'z'中的任一字母)`出现在单词中，则将该单词所代表的二进制数的第`X-'a'`位置为1。

2. **如何遍历puzzle所代表集合的子集，且该子集包含puzzle的首字母？**
	要求包含`puzzle`的首字母的子集，只要先将puzzle的首字母从集合中去掉，求出新的集合的所有子集然后再把首字母加到每个子集中即可。那么问题就变为，如何求puzzle所代表集合的子集了。这里可以直接二进制压缩遍历；也可以使用通用的「枚举二进制子集」的方法，即代码中的getSubsets函数，伪代码如下（来自LeetCode官方题解）：
		function get_subset(bitmask)
			subset = bitmask
			answer = [bitmask]
			while subset != 0
				subset = (subset - 1) & bitmask
				put subset into the answer list
			end while
			return answer
		end function
解决如上两个问题后，就可以得出求解问题的代码了。
Tip：如果一个单词中包含超过7种不同的字母，那么它不可能是谜底。

##代码
	#!C++
	class Solution {
	public:
		int getMap(string& word){
			int temp = 0;
			for(char& c: word){
				temp |= (1<<(c-'a'));
			}
			return temp;
		}
		vector<int> getSubsets(int temp){
			int subset = temp;
			vector<int> subsets(1, subset);
			while(subset){
				subset = (subset-1) & temp;
				subsets.push_back(subset);
			}
			return subsets;
		}

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
			unordered_map<int, int> mp;
			vector<int> res;
			for(string& word: words){
				int temp = getMap(word);
				if(__builtin_popcount(temp) <= 7){
					++mp[temp];
				}
			}
			for(string& puzzle: puzzles){
				int temp = getMap(puzzle) ^ (1<<(puzzle[0]-'a'));
				int ans = 0;
				vector<int> subsets = getSubsets(temp);
				for(int& subset: subsets){
					subset |= (1<<(puzzle[0]-'a'));
					ans += mp[subset];
				}
				res.push_back(ans);
			}
			return res;
		}
	};
## 用时和内存
> 执行用时：220 ms，在所有 C++提交中击败了76.92%的用户
> 内存消耗：50.6 MB，在所有 C++提交中击败了12.31%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2.26】LeetCode每日一题·猜字谜

所有评论

暂无评论

新增评论