题目描述
字谜的迷面 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]
所包含的字符都不重复。
算法
(哈希表,按位枚举) $O(words.length \cdot words[i].length + puzzles.length())$
- 对于
words
中的每个单词,统计出哪些字母出现过,将这些字母按二进制的方式进行哈希,在哈希表的对应位置加 1。例如,abab
出现过a
和b
,则key
为1 + 2 = 3
。 - 查询时,枚举
puzzles
中的每个单词。对于每个单词,枚举 0 到2^6
,代表除开头字母外,字母的组合方式。例如,aboveyz
可以有a
,ab
,ao
,abo
等组合方式。对于每种组合方式,累加在哈希表中查询对应位置上值。
时间复杂度
- 需要遍历
words
中所有单词一次,需要遍历puzzles
中的单词一次,哈希表操作的时间复杂度为常数。 - 故总时间复杂度为 $O(words.length \cdot words[i].length + puzzles.length())$。
空间复杂度
- 需要额外的空间存放哈希表以及答案数组,故空间复杂度为 $O(words.length + puzzles.length)$。
C++ 代码
class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
unordered_map<int, int> visited;
for (const auto& word: words) {
vector<bool> ch(26, false);
for (char c: word)
ch[c - 'a'] = true;
int key = 0;
for (int i = 0; i < 26; i++)
if (ch[i])
key += 1 << i;
visited[key]++;
}
int n = puzzles.size();
vector<int> ans(n, 0);
for (int i = 0; i < n; i++) {
const auto& p = puzzles[i];
int m = p.length();
for (int s = 0; s < (1 << (m - 1)); s++) {
int key = 1 << (p[0] - 'a');
for (int j = 1; j < m; j++)
if ((s >> (j - 1)) & 1)
key += 1 << (p[j] - 'a');
auto it = visited.find(key);
if (it != visited.end())
ans[i] += it -> second;
}
}
return ans;
}
};