LeetCode 792. 匹配子序列的单词数
C++爆爽,直接使用string.find
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
int cnt = 0;
for (string &word : words) { // 直接承接地址信息
int cur = -1;
bool ok = true;
for (char &c : word) {
cur = s.find(c, cur + 1); // 不断更新当前的索引下标,第二个是从什么地方开始寻找
if (cur == string::npos) {
ok = false;
break;
}
}
if (ok) cnt++;
}
return cnt;
}
};
二分的做法
class Solution {
public:
int numMatchingSubseq(string s, vector<string> &words) {
vector<vector<int>> pos(26);
for (int i = 0; i < s.size(); ++i) { // 26个字母的预处理
pos[s[i] - 'a'].push_back(i);
}
int res = words.size();
for (auto &w : words) {
if (w.size() > s.size()) {
--res;
continue;
}
int p = -1;
for (char c : w) {
auto &ps = pos[c - 'a']; // 之前的预处理就是直接找到当前的对应字母的下标
auto it = upper_bound(ps.begin(), ps.end(), p); // 在当前的下标数组中找到比当前的-1大的位置
if (it == ps.end()) {
--res;
break;
}
p = *it; // 更新当前的下标位置
}
}
return res;
}
};