97 Interleaving String

Solution-1, TLE
Similar to merge sort, but always record where to go back; so that when things fails, we go back to another branch.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if ( n1 + n2 != n3 ) return false;
        if ( n1 == 0 ) return ( s2 == s3 );
        if ( n2 == 0 ) return ( s1 == s3 );
        int i1 = 0, i2 = 0, i3 = 0;
        stack<int> back1, back2, back3;
        while ( i3 <= n3-1 ) {
            if ( (i1 <= n1-1 and s1[i1] == s3[i3] ) and (i2 == n2 or s2[i2] != s3[i3]) ) { i1++; i3++; continue;}
            if ( (i2 <= n2-1 and s2[i2] == s3[i3] ) and (i1 == n1 or s1[i1] != s3[i3]) ) { i2++; i3++; continue;}
            if ( (i1 <= n1-1 and s1[i1] == s3[i3]) and (i2 <= n2-1 and s2[i2] == s3[i3]) ) {
                back1.push(i1);
                back2.push(i2); 
                back3.push(i3);
                i1++; i3++;
                continue;
            }
            if ( back1.empty() ) return false;
            i1 = back1.top(); back1.pop();
            i2 = back2.top() + 1; back2.pop();
            i3 = back3.top() + 1; back3.pop();
        }
        return true;
    }
};

Solution-DP
A kind of brute-force DP solution. But using a matrix to deal with two strings is a common tricks! [Note to summary!]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if ( n1 + n2 != n3 ) return false;
        vector<vector<bool>> isIL(n1+1, vector<bool>(n2+1));
        // isIL[i1][i2] s1.substr(0, i1) and s2.substr(0, i2) --> s3.substr(0, i1+i2)
        isIL[0][0] = true;
        for ( int i1 = 1; i1 <= n1; i1++ ) {
            if ( s1[i1-1] == s3[i1-1] ) isIL[i1][0] = true;
            else break;
        }
        for ( int i2 = 1; i2 <= n2; i2++ ) {
            if ( s2[i2-1] == s3[i2-1] ) isIL[0][i2] = true;
            else break;
        }
        for ( int i1 = 1; i1 <= n1; i1++ ) {
            for ( int i2 = 1; i2 <= n2; i2++ ) {
                if ( s1[i1-1] == s3[i1+i2-1] and isIL[i1-1][i2] ) { isIL[i1][i2] = true; continue;}
                if ( s2[i2-1] == s3[i1+i2-1] and isIL[i1][i2-1] ) { isIL[i1][i2] = true; continue;}
            }
        }
        return isIL[n1][n2];
    }
};