97. Interleaving String - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为Dynamic Programming。

##Approach 1: space O(mn) 令dp[i][j]表示s3[0..i+j-1] is interleaving of s1[0..i-1]，s2[0..j-1]。 则：

dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1])

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

##Approach 2: space O(n) 上面方法的table可以缩减为array，因为dp[i][j]只与dp[i-1][j]和dp[i][j-1]有关。 dp[i-1][j]可用前一循环的dp[j]的值，而dp[i][j-1]在前一时刻j-1时已经计算完成，即dp[j-1]，因此一个数组dp[0..n+1]即可完成这个过程。

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