C++ clear solution beats 99.65% submits

  • 0

    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 {
        bool isSubsequence(string s, string t) {
            return findSequence(s, 0, t, 0);
        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;
                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.