[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.

DP题目，定义状态dp[i][j]表示s1长度为i的子串和s2长度为j的子串能否构成s3长度为i+j的子串，这三个子串都是从头开始的。如果dp[i-1][j]为true而且s1的i和s3的i+j相等，或者dp[i][j-1]为true而且s2的j和s3的i+j相等，那么说明dp[i][j]为true。实际实现的时候注意一下下标的问题，矩阵中的坐标比实际的要大1。

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if(m+n != s3.length())
            return false;
        boolean[][] dp = new boolean[n+1][m+1];
        
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(i == 0 && j == 0) 
                    dp[i][j] = true;
                else if(i == 0) {
                    if(dp[i][j-1] == true && s2.charAt(j-1) == s3.charAt(i+j-1))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                else if(j == 0) {
                    if(dp[i-1][j] == true && s1.charAt(i-1) == s3.charAt(i+j-1))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                else {
                    if((dp[i-1][j] == true && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] == true && s2.charAt(j-1) == s3.charAt(i+j-1)))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
            }
        }
        
        return dp[n][m];
    }