C++ clear solution beats 99.65% submits


  • 0
    D

    At first I used DP, which caused MLE (without space optimization) and TLE. Then I came up with this solution but didn't use references, instead I used substr() to get two new strings every time. Still it caused MLE. Finally I record the current index of s and t and referred the two strings and got accepted. Any comments would be appreciated. Thanks!

    class Solution {
    public:
        bool isSubsequence(string s, string t) {
            return findSequence(s, 0, t, 0);
        }
    private:
        bool findSequence(string& s, int s_index, string& t, int t_index){
            if(s_index == s.length())
                return true;
            if(t_index == t.length())
                return false;
                
            int index = t.find(s[s_index], t_index);
            if(index == string::npos)
                return false;
            else
                return findSequence(s, s_index + 1, t, index + 1);
        }
    };
    

Log in to reply
 

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