不得不说,动态规划一直以来就是我的弱项,所以解决一个动态规划的问题都得记录一下!
1. 概览
在展示思路之前,还是先来看看题。
(1).题意
给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。
(2). 样例
比如 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac",返回 true.
- 当 s3 = "aadbbbaccc", 返回 false.
(3).挑战
要求时间复杂度为O(n^2)或者更好
2.解题思路
这个题一看题意就知道用动态规划的方法来解决。求解动态规划的题,关键是在于推出动态规划的方程。
这里我先贴出动态规划的方程,然后在解释它的意思:
dp[i][j] = (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数组就是方程需要填的表。记录的是s1字符串的字符和s2的字符是否符合要求,如果符合,为true,否则为false。例如,dp[i][j],表示的意思就是说,如果s3的前i + j个字符由s1的前i个字符和s2的前j个字符组成的话,就为true,反之为false。
其次再来解释一下上面方程的意思(其实这个方程非常好理解)。我们将i换成s1.length, j换成s2.length,方程就变成了
dp[s1.length()][s2.length()] = (s1.charAt(s1.length() - 1) == s3.charAt(s1.length() + s2.length() - 1) && dp[s1.length() - 1][s2.length()])||(s2.charAt(s2.length() - 1) == s3.charAt(s1.length() +s2.length() -1) && dp[s1.length()][s2.length() - 1])
从上面变换的方程中,我们可以看出,要使dp[s1.length()][s2.length()] = true。要么使s3的最后一个字符等于s1的最后一个字符,并且s1前length - 1个字符都在s3中,也就是说dp[i - 1][j] = true;要么使s3的最后一个字符等于s2的最后一个字符,并且s2前length - 1个字符都在s3中,也就是说dp[i][j - 1] = true。如果能理解这个东西,就很好的理解之前使用ij表示的动态规划方程。
3.代码
public boolean isInterleave(String s1, String s2, String s3) {
// write your code here
if(s3.length() != s1.length() + s2.length()) {
return false;
}
if(s1.equals("") && s2.equals(s3)) {
return true;
}
if(s2.equals("") && s1.equals(s3)) {
return true;
}
boolean [][]dp = new boolean[s1.length() + 1][s2.length() + 1];
//边界条件
dp[0][0] = true;
//初始化dp[i][0]
for(int i = 1; i <= s1.length(); i++) {
dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
//初始化dp[0][i]
for(int i = 1; i <= s2.length() ; i++) {
dp[0][i - 1] = dp[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
}
for(int i = 1; i <= s1.length(); i++) {
for(int j = 1; j <= s2.length(); j++) {
dp[i][j] = (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]);
}
}
return dp[s1.length()][s2.length()];
}
我们从代码中,看到了一些情况。在正式使用动态规划方程之前,我们必须初始化dp[i][0]和dp[0][i]这种情况,因为下面循环是从i = 1和 j = 1开始的,至于为什么dp[i][0] = true和dp[0][i] = true,非常容易理解,与之前写的方程理解类似