Number of Matching Subsequeces
leetcode 792. Number of Matching Subsequences
Approach 1: Brute Force
Intuition
loop through all possibilities.
Code
cpp
int numMatchingSubseq(string s, vector<string>& words) {
unordered_map<char, deque<int>>mp;
for(int i = 0; i < s.size(); i++)
mp[s[i]].push_back(i);
int res = 0, j, cnt;
for(int i = 0; i < words.size(); i++) {
vector<int>v(words[i].size()+1, -1);
for(j = 0; j < words[i].size(); j++) {
auto it = mp[words[i][j]];
cnt = 0;
if(it.size() == 0)
break;
while(it.size() > 0 && cnt < it.size() && it[cnt] <= v[j])
cnt++;
if(cnt >= it.size())
break;
v[j+1] = it[cnt];
}
if(j==words[i].size())res++;
}
return res;
}Complextiy Analysis
Time: O(m*n)
Space: O(m+n)
Approach 2: Binary Search
Intuition
First, we store characters in string s in alpha with its indexes.
Then, simular to Approach 1, but we use binary search to identify if its a vaild word. For example, if int c = words[i][j] - 'a', but it appears that alpha[c].size() == 0 or last words' characters' indexes in s is larger than the largest element in alpha[c], then we can say this word is not vaild.
Code
cpp
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> alpha(26);
for(int i = 0; i < s.size(); i++)
alpha[s[i]-'a'].push_back(i);
int res = 0;
for(int i = 0; i < words.size(); i++) {
int pivot = -1;
bool found = true;
for(int j = 0; j < words[i].size(); j++) {
auto it = upper_bound(alpha[words[i][j]-'a'].begin(), alpha[words[i][j]-'a'].end(), pivot);
if(it == end(alpha[words[i][j]-'a']))
found = false;
else
pivot = *it;
}
if(found)
res++;
}
return res;
}Complextiy Analysis
Time: O(log(m)*n)
Space: O(m)
Approach 3: Trie
Intuition
First, we have a vector to store words base on its back() char.
Second, we loop through s form end to begin, check s[i] key in vector, and reallocate words stored in vector[s[i]] using first step, and repeat that.
Code
cpp
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<string>> w(126);
for(auto& i : words)
w[i.back()].push_back(i);
int res = 0;
for(int i = s.size()-1; i >= 0; i--) {
auto temp = w[s[i]];
w[s[i]].clear();
for(auto& j : temp) {
j.pop_back();
if(j.size() == 0) res++;
else w[j.back()].push_back(j);
}
}
return res;
}Complextiy Analysis
Time: O(m*log(n))
Space: O(n)
Some Super Dope Code Exhibition
Approach 3
from @mzchen
cpp
int numMatchingSubseq(string S, vector<string>& words) {
vector<string::iterator> waiting[128];
for (auto &word : words)
waiting[word[0]].emplace_back(word.begin());
for (char c : S) {
vector<string::iterator> advance;
swap(advance, waiting[c]);
for (auto in : advance)
waiting[*++in].emplace_back(in);
}
return waiting[0].size();
}