-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
1178.cpp
156 lines (131 loc) · 4.2 KB
/
1178.cpp
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
__________________________________________________________________________________________________
sample 136 ms submission
class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
vector<int> ans;
unordered_map<int, int> freq;
for (const string& word : words) {
int mask = 0;
for (char c : word)
mask |= 1 << (c - 'a');
++freq[mask];
}
for (const string& p : puzzles) {
int mask = 0;
for (char c : p)
mask |= 1 << (c - 'a');
int first = p[0] - 'a';
int curr = mask;
int total = 0;
while (curr) {
if ((curr >> first) & 1) {
auto it = freq.find(curr);
if (it != freq.end()) total += it->second;
}
curr = (curr - 1) & mask;
}
ans.push_back(total);
}
return ans;
}
};
__________________________________________________________________________________________________
sample 140 ms submission
class Solution {
public:
inline void setBit(int& bits, int pos) {
bits |= 1 << pos;
}
const int checkSubset(int& bits, int pos, const string& s, const unordered_map<int, int>& wordSets) {
if (pos == s.size()) {
auto found = wordSets.find(bits);
return found != wordSets.end() ? found->second : 0;
}
int tmp = bits;
// check with the bit unset
int res = checkSubset(bits, pos + 1, s, wordSets);
// check with the bit set
setBit(bits, s[pos] - 'a');
res += checkSubset(bits, pos + 1, s, wordSets);
// reset
bits = tmp;
return res;
}
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
vector<int> res;
res.reserve(puzzles.size());
// build bit sets
unordered_map<int, int> wordSets;
for (const auto& word: words) {
int bits = 0;
for (char c: word) {
setBit(bits, c - 'a');
}
wordSets[bits]++;
}
for (const auto& puzzle: puzzles) {
// the first bit is always set
int bits = 0;
setBit(bits, puzzle[0] - 'a');
// collect occurences for all possible subsets
int cnt = checkSubset(bits, 1, puzzle, wordSets);
res.push_back(cnt);
}
return res;
}
};
__________________________________________________________________________________________________
sample 144 ms submission
class Solution {
public:
inline void setBit(int& bits, int pos)
{
bits |= 1 << pos;
}
const int checkSubset(int& bits, int pos, const string& s, const unordered_map<int, int>& wordSets)
{
if (pos == s.size())
{
auto found = wordSets.find(bits);
return found != wordSets.end() ? found->second : 0;
}
int tmp = bits;
//for each character in a puzzle word, either use it or not use it! 2^6 choices
// check with the bit unset
int res = checkSubset(bits, pos + 1, s, wordSets);
// check with the bit set
setBit(bits, s[pos] - 'a');
res += checkSubset(bits, pos + 1, s, wordSets);
// reset
bits = tmp;
return res;
}
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles)
{
vector<int> res;
res.reserve(puzzles.size());
// build bit sets
unordered_map<int, int> wordSets; // word(bit format) -> appearance:
// abcd adcb the same map, appears twice!
for (const auto& word: words)
{
int bits = 0;
for (char c: word)
{
setBit(bits, c - 'a');
}
wordSets[bits]++;
}
for (const auto& puzzle: puzzles)
{
// the first bit is always set
int bits = 0;
setBit(bits, puzzle[0] - 'a');
// collect occurences for all possible subsets (for exery puzzle word)
int cnt = checkSubset(bits, 1, puzzle, wordSets);
res.push_back(cnt);
}
return res;
}
};