LeetCode: Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

---

The problem can be solved by simple recursion. If s1[0] == s3[0], then go on check s1[1:],s2 and s3[1:]. If s2[0] == s3[0], then go on check s1, s2[1:] and s3[1:]. If s1[0] == s2[0] == s3[0], then go on check s1[1:],s2 and s3[1:] and s1, s2[1:] and s3[1:]. However the recursive solution cannot pass large test case. So we modify it to a dynamic programming way. Let checker[i][j] represent s1[0..i] and s2[0..j] can be matched in s3.

C++ Code:

/*
 * func: is_interleaved
 * goal: to check s3 is formed by interleaving s1 and s2
 * @param s1: string s1
 * @param s2: string s2
 * @param s3: string s3
 * return: true or false
 */
/*
 * DP, checker[i][j] means if interleaving s1[0..i] and s2[0..j] can be matched
 * complexity: time O(mn), space O(mn)
 */
bool is_interleaved(string s1, string s2, string s3){
    if(s1.length() + s2.length() != s3.length()){
        return false;
    }
    
    vector<vector<bool> > checker(s1.length()+1, vector<bool>(s2.length()+1, false));
    checker[0][0] = true;
    for(int i=1; i<=s1.length(); ++i){
        if(s1[i-1] == s3[i-1] && checker[i-1][0]){
            checker[i][0] = true;
        }
    }
    for(int j=1; j<=s2.length(); ++j){
        if(s2[j-1] == s3[j-1] && checker[0][j-1]){
            checker[0][j] = true;
        }
    }
    for(int i=1; i<=s1.length(); ++i){
        for(int j=1; j<=s2.length(); ++j){
            checker[i][j] = (checker[i-1][j] && s1[i-1] == s3[i+j-1]) || (checker[i][j-1] && s2[j-1] == s3[i+j-1]);
        }
    }
    return checker[s1.length()][s2.length()];
}

Python Code:

# func: check if s3 is formed by interleaving s1 and s2
# @param s1: string s1
# @param s2: string s2
# @param s3: string s3
# @return: True or False
# Complexity: time O(mn), space O(mn)
def is_interleaved(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    checker = [[False] * (len(s2) + 1) for _ in xrange(len(s1)+1)]
    checker[0][0] = True
    for i in xrange(1, len(s1)+1):
        if s1[i-1] == s3[i-1] and checker[i-1][0]:
            checker[i][0] = True

    for j in xrange(1, len(s2)+1):
        if s2[j-1] == s3[j-1] and checker[0][j-1]:
            checker[0][j] = True

    for i in xrange(1, len(s1)+1):
        for j in xrange(1, len(s2)+1):
            checker[i][j] = (checker[i-1][j] and s1[i-1] == s3[i+j-1]) or (checker[i][j-1] and s2[j-1] == s3[i+j-1])

    return checker[len(s1)][len(s2)]