给定字符串 S 和单词字典 words,
求 words[i] 中是 S
的子序列的单词个数。
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。注意:
words和 S
里的单词都只由小写字母组成。S 的长度在 [1, 50000]。words 的长度在
[1, 5000]。words[i]的长度在[1, 50]。执行用时 :1136 ms, 在所有 cpp 提交中击败了5.05%的用户
内存消耗 :136 MB, 在所有 cpp 提交中击败了18.75%的用户
int numMatchingSubseq(string S, vector<string>& words) {
unordered_map<char, set<int>> mp;
for (unsigned i = 0; i < S.size(); ++i) {
mp[S[i]].insert(i);
}
int count = 0,temp;
unsigned i = 0;
for (auto& word : words) {
temp = *(mp[word[0]].begin());
for (i = 1; i < word.size(); ++i) {
auto pos = mp[word[i]].upper_bound(temp);
if (pos != mp[word[i]].end()) {
if (*pos > temp) temp = *pos;
else
break;
}
else
break;
}
if (i == word.size()) count++;
}
return count;
}执行用时 :308 ms, 在所有 cpp 提交中击败了58.08%的用户
内存消耗 :40.5 MB, 在所有 cpp 提交中击败了65.63%的用户
int numMatchingSubseq(string S, vector<string>& words) {
unordered_map<char, vector<int>> mp;
for (unsigned i = 0; i < S.size(); ++i) {
mp[S[i]].push_back(i);
}
int count = 0,temp;
unsigned i;
for (auto& word : words) {
if (mp.find(word[0]) == mp.end()) //时刻注意判断问题
continue;
temp = *(mp[word[0]].begin());
for (i = 1; i < word.size(); ++i) {
if (mp.find(word[i]) == mp.end()) //时刻注意判断有无问题
break;
auto pos = upper_bound(mp[word[i]].begin(), mp[word[i]].end(),temp);
if (pos != mp[word[i]].end()) {
temp = *pos;
}
else
break;
}
if (i==word.size()) count++;
}
return count;
}