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.

Solution1: 2D dp

“When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. ”

这道题思路是，s1取一部分s2取一部分，看最后是否能匹配s3。

定义一个boolean二维数组dp[i][j]表示： s1取前i位，s2取前j位，是否能组成s3的前i+j位。

首先，假设s2为空，将s1每一位跟s3匹配放入dp[i][0]；假设s1为空，将s2每一位跟s3匹配放入dp[0][j]。

如果不等就是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）。
时间上因为是一个二维动态规划，所以复杂度是O(m*n)，m和n分别是s1和s2的长度。空间复杂度是O(m*n).

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

Reference: http://blog.csdn.net/u011095253/article/details/9248073
Solution2: 1D dp
思路和soluton1一样，动态规划的递推式为：
res[i][j] = res[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)
可以看出递推式中只需要用到上一行的信息，所以我们只需要一个一维数组就可以完成历史信息的维护，为了更加优化，把短的字符串放在内层循环，这样就可以只需要短字符串的长度即可，所以空间复杂度是O(min(m,n))。时间复杂度还是O(m*n)。

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

        return dp[minStr.length()];
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/24683159