Two c++ solutions: one recursive, one memorization


  • 0
    H

    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;
        }
    };
    

  • 0

    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!


Log in to reply
 

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