Anyone can give a look and see reason of runtime error


  • 0
    W
    class Solution {
    public:
        bool ans = false;
        string s1, s2, s3;
        int len1 =0, len2 =0, len3= 0;
        void solve(int first, int second, string final)
        {
            if((first == len1) && (second == len2))
            {
                if(final == s3)
                    ans = true;
                return;
            }
            if(first == len1)
                solve(first, second+1, final + s2[second]);
            else if(second == len2)
                solve(first+1, second, final + s1[first]);
            solve(first, second+1, final + s2[second]);
            solve(first+1, second, final + s1[first]);
            
        }
        bool isInterleave(string sOne, string sTwo, string sThree) {
            s1 = sOne; s2 = sTwo; s3 = sThree;
            if(s1 != "")
                len1 = s1.size(); 
            if(s2 != "")
                len2 = s2.size();
            if(s3 != "")
                len3 = s3.size(); 
          //  return ans;
            solve(0, 0, "");  
            return ans;
        }
    };
    

    My code is getting run time error and I am unable to find why?
    Any help with that?


  • 0
    J

    The time complexity of this code may be O(2^n), would it possible to be stack overflow?


  • 0
    W

    Why do you think time complexity will be O(2^n)?


  • 0
    A

    because everytime, you have 2 choises:go string s1 or string s2; so it is O(2^min(s1.size(),s2.size))


Log in to reply
 

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