1178. Number of Valid Words for Each Puzzle
With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:
- word contains the first letter of puzzle.
- For each letter in word, that letter is in puzzle.
- For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”, while
- invalid words are “beefed” (does not include ‘a’) and “based” (includes ‘s’ which is not in the puzzle).
Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
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
50
51
52
53
54
55
56
57
58
| struct Trie{
Trie* next[2];
int count = 0;
Trie() {
memset(next, 0, sizeof(next));
}
void insert(int mask, int i = 0) {
if(i == 26) {count++;return;}
bool key = (mask & (1<<i));
if(!next[key]) next[key] = new Trie();
next[key]->insert(mask, i + 1);
}
int find(int mask, int must, int i = 0) {
if(i == 26) return count;
if(must == i) {
if(next[1])
return next[1]->find(mask, must, i + 1);
else return 0;
} else {
if(mask & (1<<i)) {
int res = 0;
if(next[0])
res += next[0]->find(mask, must, i + 1);
if(next[1])
res += next[1]->find(mask, must, i + 1);
return res;
} else {
if(next[0])
return next[0]->find(mask,must,i+1);
return 0;
}
}
}
};
class Solution {
int toMask(string& s) {
int mask = 0;
for(auto ch : s)
mask |= 1<<(ch-'a');
return mask;
}
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
Trie* trie = new Trie();
for(auto w: words) {
int mask = toMask(w);
trie->insert(mask);
}
vector<int> res;
for(auto puzzle : puzzles) {
int mask = toMask(puzzle);
int ans = trie->find(mask, puzzle[0]-'a');
res.push_back(ans);
}
return res;
}
};
|
