Interleaving String

给三个字符串, S1,S2,S3. 问S3是不是S1和S2交叉在一起. 这个题用dp来做. dp[i][j] 表示s1的前i和s2的前j个字符能组成s3的前i+j个字符. 那么是true. 这个dp最难的是初始化.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        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() + 1; 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() + 1; 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() + 1; i++) {  
            for(int j = 1; j < s2.length() + 1; j++) {  
                if (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) {  
                    dp[i][j] = true;  
                }  
                if (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) {  
                    dp[i][j] = true;  
                }  
            }  
        }  
        return dp[s1.length()][s2.length()];  
    }  
}