Two c++ solutions: one recursive, one memorization

• This recursive solution is for the original question.

``````class Solution {
public:
bool isSubsequence(string s, string t) {
return helper(s, t, 0, 0);
}

bool helper(string& s, string& t, int si, int ti) {
if (si == s.size()) return true;
int p = t.find(s[si], ti);
if (p == string::npos) return false;
else return helper(s, t, si+1, p+1);
}
};
``````

This solution is to store all positions of each character into a vector of vector, i.e. `vector<vector<int>>`, when there are a lot of S strings, instead of iterating the whole T string, we only need to check the positions of each character in S and try to find the minimum index which is not less than the `bound`.

``````class Solution {
public:
bool isSubsequence(string s, string t) {
// memo should be initialized in constructor
vector<vector<int>> memo(26);
for (int i = 0; i < t.size(); i++) {
memo[t[i]-'a'].push_back(i);
}
// the code below should belong to a separate member function
int bound = 0;
for (int i = 0; i < s.size(); i++) {
auto v = memo[s[i]-'a'];
auto itr = lower_bound(v.begin(), v.end(), bound);
if (itr == v.end()) return false;
bound = *itr + 1;
}
return true;
}
};
``````

• So, use memo here is to record every letter position in string t, such that we don't need to check every single s_i from t[0]. Instead, find char from bound.
The way to " bound = *itr + 1; " is to jump substantially in string t.

do I understand you algorithm correctly? Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.