Recursive C++ works, but I don't know why


  • 1
    L

    I started with a straight forward recursive algorithm that basically does DFS (branching point at the [2 matches] case in the code, where s1 and s2 has the same first characters) and it got TLE.
    After some struggling, I made a small modification to the DFS, that is instead of advancing 1 character, I made it advance till the character changes. The code got accepted (5-12ms), and I dont know why lol, since the complexity should be basically the same.

    class Solution {
    public:
        bool isInterleave(const string & s1, const string & s2, const string & s3, int p1 = 0, int p2 = 0, int p3 = 0) {
            
            
            while (true)
            {
                // done
                if (p1 == s1.length() && p2 == s2.length() && p3 == s3.length())
                    return true;
                
                // 2 matches
                else if (p1 < s1.length() && p2 < s2.length() && p3 < s3.length() && s1[p1] == s3[p3] && s2[p2] == s3[p3])
                {
                    // choose s1
                    for (int i = 0; true; i++)
                        if (!(p1 + i < s1.length() && p3 + i < s3.length() && s1[p1 + i] == s1[p1] && s3[p3 + i] == s1[p1]))
                        {   // insert i character from s1 to s3, so advance p1 and p3 by i
                            // check if this choice is correct
                            if (isInterleave(s1, s2, s3, p1+i, p2, p3+i))
                                return true;  
                            break;
                        }
                        
                    // choose s2
                    for (int i = 0; true; i++)
                        if (!(p2 + i < s2.length() && p3 + i < s3.length() && s2[p2 + i] == s1[p1] && s3[p3 + i] == s1[p1]))
                        {   // insert i character from s2 to s3, so advance p2 and p3 by i
                            if (isInterleave(s1, s2, s3, p1, p2+i, p3+i))
                                return true;  
                            break;
                        }   
                    
                    // both 2 choices don't work
                    return false;
                }
                // 1 matches
                else if (p1 < s1.length() && p3 < s3.length() && s1[p1] == s3[p3])
                {
                    p1++;
                    p3++;
                }
                else if (p2 < s2.length() && p3 < s3.length() && s2[p2] == s3[p3])
                {
                    p2++;
                    p3++;
                }
                // no match
                else
                    return false;
            }
            
        }
    };

  • 0
    P

    I think the recursive solution does not re use the results of sub problems already calculated unless you use memiozation. The same thing happened to me and I changed my solution to normal DP w/o recursion and it worked like a charm.


  • 0
    A
    This post is deleted!

  • 0
    A

    I use recursition and got wrong answer because I cant figure out in case of two match, but I didnt consider to compare only same substring.


Log in to reply
 

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