首页 > 代码库 > LintCode刷题笔记-- InterLeaving
LintCode刷题笔记-- InterLeaving
动态规划
解题思路
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()]; }
LintCode刷题笔记-- InterLeaving