/
792.cpp
65 lines (64 loc) · 2.07 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
__________________________________________________________________________________________________
sample 76 ms submission
static const auto _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return 0;
}();
class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
int N = words.size();
int current_index[N] = {0};
queue <int> next[26];
for(int i = 0; i < N; i++)
next[words[i][0] - 'a'].push(i);
for(const auto& character : S)
{
int temp = next[character - 'a'].size();
for(int i = 0; i < temp; i++)
{
int word_index = next[character - 'a'].front();
next[character - 'a'].pop();
current_index[word_index]++;
if(current_index[word_index] < words[word_index].length())
next[words[word_index][current_index[word_index]] - 'a'].push(word_index);
}
}
int matching_subsequences = 0;
for(int i = 0; i < N; i++)
if(current_index[i] == words[i].length())
matching_subsequences++;
return matching_subsequences;
}
};
__________________________________________________________________________________________________
sample 23860 kb submission
class Solution {
bool isSub(string const & s, string & word) {
if (word.length() > s.length())
return false;
int i = 0, j = 0;
while (i < word.length()) {
if (j >= s.length())
return false;
if (word[i] == s[j])
++i;
++j;
}
return true;
}
public:
int numMatchingSubseq(string S, vector<string>& words) {
int result = 0;
for (auto & word : words) {
if (isSub(S, word)) {
//cout << "it is " << word << endl;
++result;
}
}
return result;
}
};
__________________________________________________________________________________________________