Мое замешательство связано с решением проблемы 792. Число совпадающих подпоследовательностей в leetcode, наивное решение состоит в том, чтобы проверять все символы в S для каждого искомого слова.
Временная сложность слишком высока, чтобы ее можно было выполнить. пройти все тестовые примеры, как указано в официальном ответе.
Первый фрагмент кода, указанный ниже, может превзойти 100% просто потому, что он вызывает функцию string::find_first_of, в то время как мой написанный от руки коды используют точно такую же процедуру (я думаю), получают TLE, как и ожидалось.
Итак, почему первый из них такой быстрый?
// comes from the second solution post in leetcode-cn
class Solution {
public:
int numMatchingSubseq(string S, vector& words) {
int res = 0, j;
for (int i = 0; i < words.size(); i ++) {
int position = -1;
for (j = 0; j < words.size(); j ++) {
position = S.find_first_of(words[j], position + 1);
if (position == -1) break;
}
if (j == words.length()) res ++;
}
return res;
}
};
версия 2, написанная от руки. Превышение лимита времени
static inline int find_first_of(const string & s, char & c, int st) {
int n = s.size() - st;
const char * data = s.data(), * cur = data + st;
for (std::size_t i = 0; i < n; ++i) {
if (cur == c)
return cur + i - data;
}
return -1;
}
class Solution {
public:
int numMatchingSubseq(string S, vector& words) {
int res = 0, j;
for (int i = 0; i < words.size(); i ++) {
int position = -1;
for (j = 0; j < words.size(); j ++) {
position = find_first_of(S, words[j], position + 1);
if (position == -1) break;
}
if (j == words.length()) res ++;
}
return res;
}
};
Подробнее здесь: https://stackoverflow.com/questions/630 ... d-first-of
