Interleaving String leetcode

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.

思路: 来自http://blog.csdn.net/u011095253/article/details/9248073

dp[i][j]表示s1取前i位，s2取前j位，是否能组成s3的前i+j位

举个列子，注意左上角那一对箭头指向的格子dp[1][1], 表示s1取第1位a, s2取第1位d，是否能组成s3的前两位aa

从dp[0][1] 往下的箭头表示，s1目前取了0位，s2目前取了1位，我们添加s1的第1位，看看它是不是等于s3的第2位，( i + j 位）

从dp[1][0] 往右的箭头表示，s1目前取了1位，s2目前取了0位，我们添加s2的第1位，看看它是不是等于s3的第2位，( i + j 位)

那什么时候取True，什么时候取False呢？

False很直观，如果不等就是False了嘛。

那True呢？首先第一个条件，新添加的字符，要等于s3里面对应的位( i + j 位)，第二个条件，之前那个格子也要等于True

举个简单的例子s1 = ab, s2 = c, s3 = bbc ，假设s1已经取了2位，c还没取，此时是False（ab!=bb），我们取s2的新的一位c，即便和s3中的c相等，但是之前是False，所以这一位也是False

同理，如果s1 = ab, s2 = c, s3=abc ，同样的假设，s1取了2位，c还没取，此时是True（ab==ab），我们取s2的新的一位c,和s3中的c相等，且之前这一位就是True，此时我们可以放心置True （abc==abc)

state: dp[i][j] s1取前i个字符 s2取前j个字符 s3取前i+1字符 是否能匹配
function:  如果最后一位(i+j位)与s1的最后一位(i位)相等 dp[i][j] = dp[i-1][j]
与s2最后一位相等则dp[i][j] = dp[i][j-1]
initial: dp[0][0] = true dp[i][0] dp[0][j]看s1 s2 s3比较
返回: dp[s1.length][s2.length]
时间和空间都是O(m * n)

声明数组dp[s1.length+1][s2.length+1] string 的index 和dp的index 相差1

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if (l1 + l2 != l3) {
            return false;
        }
        boolean [][] dp = new boolean[l1+1][l2+1];
        dp[0][0] = true;
        for (int i = 1; i <= l1; i++) {
            if (s3.charAt(i-1) == s1.charAt(i-1) && dp[i-1][0]) {
                dp[i][0] = true;
            }
        }
        for (int j = 1; j <= l2; j++) {
            if (s3.charAt(j-1) == s2.charAt(j-1) && dp[0][j-1]) {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i<= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j]) {
                    dp[i][j] = true;
                }
                if (s3.charAt(i+j-1) == s2.charAt(j-1) && dp[i][j-1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[l1][l2];
    }
}