标签：

动态规划

解题思路

1. 这道题最重要的是，存在三个字符串，但是并不需要两个二维矩阵来进行解，因为可以使用i+j-1来代表s3的下标，这样就可以通过i和j来遍历s3了。因为对于任何一个合法的交叉字符串都会有，s3(i+j-1)=s1(i-1) 或者s3(i+j-1) = s2(j-1)

2. 所以对于动态规划矩阵就可以在s1,s2这两个向量上进行分解，有dp[i][j], 其所代表的意义的是在s3(i+j-1)的位置上是否存在有s1(i)或者s2(j)与其相等，

3.如果结果返回true，证明是一对交叉字符串，对于矩阵中的每一个点都会存在其上方或者左方有一个点为true。因为在s3中的前一个节点会有s1或者s2中的一个点来进行匹配，也可能存在两者都相等，这样的情况中，左方和上方的解应当都为true。

4. 对于初始状态，也是最懵逼的，看答案想了很久没有明白：分别遍历s1与s2，与s3进行比较，找出s1或者s2的前几项与s3。找出矩阵的入口，因为如果两个字符串为合法的交叉字符串的话，至少dp[i][0]或者dp[0][j]中至少有一个序列中存在两个true，其中dp[0][0]为true。

对于dp的解法：

s1 = a1, a2 ……..a(i-1), ai
s2 = b1, b2, …….b(j-1), bj
s3 = c1, c3, …….c(i+j-1), c(i+j)

定义 match[i][j] 意味着，S1的(0, i)和S2的(0,j)，匹配与S3的(i+j)
如果 ai == c(i+j), 那么 match[i][j] = match[i-1][j]， 等价于如下字符串是否匹配。

s1 = a1, a2 ……..a(i-1)
s2 = b1, b2, …….b(j-1), bj
s3 = c1, c3, …….c(i+j-1)

同理，如果bj = c(i+j), 那么match[i][j] = match[i][j-1];

5.参考代码：

public boolean isInterleave(String s1, String s2, String s3) {
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]==true){
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\]==true){  
            dp\[0\]\[j\] = true;  
        }  
    }

    for(int i = 1; i<=s1.length(); i++){  
        for(int j = 1; j<=s2.length(); j++){  
            if(s1.charAt(i-1)==s3.charAt(i+j-1)&&dp\[i-1\]\[j\]||  
               s2.charAt(j-1)==s3.charAt(i+j-1)&&dp\[i\]\[j-1\]){  
                   dp\[i\]\[j\] = true;  
               }  
        }  
    }  
    return dp\[s1.length()\]\[s2.length()\];  
}