-
Notifications
You must be signed in to change notification settings - Fork 3
/
792.cpp
47 lines (43 loc) · 1.55 KB
/
792.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
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
int count = 0;
vector<vector<pair<int, int>>> hash(26);
for (int i = 0; i < words.size(); ++i) {
auto& word = words[i];
hash[word[0] - 'a'].push_back(make_pair(i, 1));
}
for (auto c : s) {
vector<pair<int, int>> collect;
for (auto [idx, j] : hash[c - 'a']) {
if (words[idx].size() == j) count++;
else if (words[idx][j] == c) {
collect.push_back(make_pair(idx, j + 1));
}
else hash[words[idx][j] - 'a'].push_back(make_pair(idx, j + 1));
}
hash[c - 'a'] = collect;
}
return count;
}
};
// V2
// class Solution {
// public:
// int numMatchingSubseq(string s, vector<string>& words) {
// vector<vector<pair<int, int>>> positions(26); // {alphabet}->{{id, position}}
// int res = 0;
// for (int i = 0; i < words.size(); ++i) {
// positions[words[i][0] - 'a'].push_back(make_pair(i, 1));
// }
// for (int i = 0; i < s.size(); ++i) {
// auto vec = positions[s[i] - 'a'];
// positions[s[i] - 'a'].clear();
// for (auto p : vec) {
// if (words[p.first].size() == p.second) res++;
// else positions[words[p.first][p.second] - 'a'].push_back(make_pair(p.first, p.second + 1));
// }
// }
// return res;
// }
// };