给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是none),而不改变其余字符的相对顺序。
例如, “ace” 是 “abcde” 的子序列。
示例 1:
输入: s = “abcde”, words = [“a”,”bb”,”acd”,”ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。
手写二分
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> pos(26);
int n = s.size(), m = words.size();
for(int i = 0; i < n; i ++){
pos[s[i] - 'a'].push_back(i);
}
int res = 0;
for(auto word : words){
int pre = -1;
bool flag = true;
for(auto c : word){
int t = c - 'a';
if(!(pos[t].size())){
flag = false;
break;
}
else if(pre == -1) pre = pos[t][0];
else{
int l = 0, r = pos[t].size() - 1;
while(l < r){
int mid = (l + r) >> 1;
if(pos[t][mid] > pre) r = mid;
else l = mid + 1;
}
if(pos[t][l] <= pre){
flag = false;
break;
}
else{
pre = pos[t][l];
}
}
}
if(flag) res ++;
}
return res;
}
};
upper_bound
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> pos(26);
int n = s.size(), m = words.size();
for(int i = 0; i < n; i ++){
pos[s[i] - 'a'].push_back(i);
}
int res = 0;
for(auto word : words){
int pre = -1;
bool flag = true;
for(auto c : word){
int t = c - 'a';
auto it = upper_bound(pos[t].begin(), pos[t].end(), pre);
if(it == pos[t].end()){
flag = false;
break;
}
else pre = *it;
}
if(flag) res ++;
}
return res;
}
};