Day 85, #97, Interleaving String

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.
------------------------------------------------------
Solution #1, straight forward recursion 

class Solution {
public:
    bool isInter(string s1, int i1, string s2, int i2, string s3, int i3) {
        if (i3 == s3.length()) {
            return true;
        }
        
        if (i1 < s1.length() && s1[i1] == s3[i3] && isInter(s1,i1 + 1,s2,i2,s3,i3 + 1)) {
            return true;
        }
        
        if (i2 < s2.length() && s2[i2] == s3[i3] && isInter(s1,i1,s2,i2 + 1,s3,i3 + 1)) {
            return true;
        }
        
        return false;
        
    }

    bool isInterleave(string s1, string s2, string s3) {
        return isInter(s1,0,s2,0,s3,0);
    }
};

Solution #2 DP, similar logi. dp[i][j] means if s1[0 : i] and s2[0 : j] can match s3[0 : i + j + 1]
不用检查s3[0]是因为，只有在s1或s2长度为0时，s3[0]才有被检查的必要，这我们已经在initialization的时候已经做过 
***一定要想清楚 dp[i][j] 所代表的意思***

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 + len2 != s3.length()) return false;
        
        // check empty strings
        if (len1 == 0) {
            if (s2 == s3) {
                return true;
            }else {
                return false;
            }
        }
        if (len2 == 0) {
            if (s1 == s3) {
                return true;
            }else {
                return false;
            }
        }
        
        vector<vector<bool> > dp(len1 + 1,vector<bool>(len2 + 1,false));
        
        // initialize dp
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            if (s1[i - 1] == s3[i - 1]) {
                dp[i][0] = true;
            }else {
                break;
            }
        }
        
        for (int i = 1; i <= len2; i++) {
            if (s2[i - 1] == s3[i - 1]) {
                dp[0][i] = true;
            }else {
                break;
            }
        }
        
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (s1[i] == s3[i + j + 1] && dp[i][j + 1]) {
                    dp[i + 1][j + 1] = true;
                }
                
                if (s2[j] == s3[i + j + 1] && dp[i + 1][j]) {
                    dp[i + 1][j + 1] = true;
                }
            }
        }
        
        return dp[len1][len2];
    }
};

可以简化为O(n) space, 就不写了