Leetcode 97: 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.

二维DP 

 这个题目拿到后分析下发现可以用dp做，一开始的想法是要知道m[0][n]是不是，可以看m[0][n-1]是不是，最后一个字符可以来自s1, 可以来自s2，但是有个问题，如果仅仅用一维dp做的话，不知道最后一个字符对应于s1或者s2的哪个index，因为不知道s3前面的s1, s2的字符组合是哪样的， 所以最后还是要用二维dp，并且M[i][j]的意思是取s1前i个字符，取s2前j个字符，最后interleaving组成s3的 i+j个字符。 要看M[i][j]可以看i-1,j，说明最后一个字符来自s1， 或者i,j-1说明最后一个字符来自s2，并且对应s1,s2相应的位置上。 这样一来，dp的递推式就得到了。
二维dp主要是不容易看出递推式。


class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        //dp: dp[i][j] : s1 0-i s2 0-j s3:i+j
        if (s1.size() + s2.size() != s3.size()) return false;
       
        bool dp[s1.size()+1][s2.size()+1];
        //base case
        dp[0][0] = true;
        for (int i = 1; i < s1.size()+1; i++) {
            if (s1[i-1] == s3[i-1] && dp[i-1][0]) {
                dp[i][0] = true;
            } else {
                dp[i][0] = false;
            }
        }
        for (int j = 1; j < s2.size()+1; j++) {
            if (s2[j-1] == s3[j-1] && dp[0][j-1]) {
                dp[0][j] = true;
            } else {
                dp[0][j] = false;
            }
        }
        for (int i = 1; i < s1.size()+1; i++) {
            for (int j = 1; j < s2.size()+1; j++) {
                if (s1[i-1] == s3[i+j-1] && dp[i-1][j]) {
                    dp[i][j] = true;
                    continue;
                }
                if (s2[j-1] == s3[i+j-1] && dp[i][j-1]) {
                    dp[i][j] = true;
                    continue;
                }
                dp[i][j] = false;
            }
        }
        return dp[s1.size()][s2.size()];
    }
};