У меня проблема с Leetcode, которая называется " Количество соответствующих подпоследовательностей ".Вам дана строка S и вектор более мелких строк, и вы должны выяснить, сколько из меньших строк являются подстроками S. (Не обязательно непрерывные подстроки.)
Я написал свой код в определенномКстати, и хотя он работает нормально, это было так, что таймер компилятора на Leetcode.Кто-то еще написал свой код почти так же, как мой, но время не истекло.Мне интересно, что делает его быстрее.Вот мое:
class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
int count = 0;
vector<set<int>> Svec (26); // keep track of the indices where characters were seen in S
for (int i = 0; i < S.length(); ++i) Svec[S[i] - 'a'].insert(i);
for (auto & w : words) { // loop over words and characters within words, finding the soonest the next character appears in S
bool succeeded = true;
int current_index = -1;
for (auto & c : w) {
set<int> & c_set = Svec[c - 'a'];
auto it = upper_bound(begin(c_set), end(c_set), current_index);
if (it == end(c_set)) {
succeeded = false;
break;
}
current_index = *it;
} // loop over chars
if (succeeded) count++;
} //loop over words
return count;
}
};
int main() {
string S = "cbaebabacd";
vector<string> words {"abc", "abbd", "bbbbd"};
Solution sol;
cout << sol.numMatchingSubseq(S, words) << endl;
return 0;
}
Выходы
2
Program ended with exit code: 0
Его решение хранит индексы не в vector<set<int>>, а в vector<vector<int>>.Я не понимаю, почему это было бы большой разницей.
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 (const auto& word : words) {
int x = -1;
bool found = true;
for (char c : word) {
auto it = upper_bound (alpha[c - 'a'].begin (), alpha[c - 'a'].end (), x);
if (it == alpha[c - 'a'].end ()) found = false;
else x = *it;
}
if (found) res++;
}
return res;
}