网站后台模块,wordpress输出标签下文章,能挣钱的平台 正规的,广东网站营销seo费用介绍
编程语言#xff1a;Java 本篇介绍一道比较经典的二维动态规划题。 交错字符串
主要说明几点#xff1a;
为什么双指针解不了#xff1f;为什么是二维动态规划#xff1f;根据题意分析处转移方程。严格位置依赖和空间压缩优化。
题目介绍 题意有点抽象#xff0c…介绍
编程语言Java 本篇介绍一道比较经典的二维动态规划题。 交错字符串
主要说明几点
为什么双指针解不了为什么是二维动态规划根据题意分析处转移方程。严格位置依赖和空间压缩优化。
题目介绍 题意有点抽象 看一下示例吧。 第一种理解方式就是保持两个字符串相对顺序不变 将s2切割成一个一个子串插入到s1中 看能否构成字符串s3。
第二种理解方式是字符串s3是根据s1,s2保持相对顺序字符选择的结果。 因为保持各个字符串之间相对顺序不变 那么可以尝试双指针的思路 比如如上图 s3的第一个和第二个字符只能来自s1, 第3个字符只能来自s2, 第4个字符有讲究了 它既可能来自s1也可能来自s2 那么到底来自哪儿 都有可能 下面分析这种双指针为什么是错误的。 双指针的错误解法
部分朋友看到题相对次序不变 很容易想到归并排序的merge部分 自然而然的写出了 如下代码。
class Solution {public boolean isInterleave(String str1, String str2, String str3) {char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();char[] s3 str3.toCharArray();if(s1.length s2.length ! s3.length){return false;}int p1 0, p2 0;int i 0;while(p1s1.lengthp2s2.length){if(s1[p1]s3[i]){p1;i;}else if(s2[p2]s3[i]){p2;i;}else{return false;}}while(p1s1.length){if(s1[p1]!s3[i]){return false;}}while(p2s2.length){if(s2[p2]!s3[i]){return false;}}return true;}
}大部分测试用例能过 说明双指针的思想大概率是对的 但是对于某些情况误判了。 误判了什么 即字符串str1和str2的异步双指针 在某些情况会出现指向相同字符的情况。 正如下图 此刻双指针只能固定的选择一种方案 要么选择str1匹配 要么选择str2匹配。 实际最终是否能交错处str3 取决于两种方案的并集。 双指针显然错过了一种方案 况且这次选择后面可能还要遇见相同字符的分类方案。 因此 这道题是动态分析 应该动态规划分类讨论处理结果。
方法1递归入手改写记忆化搜索
双指针没有处理分类讨论 那么通过递归分情况讨论不就好了。 直接定义一个函数f(n), f(s1, p1, s2, p2, s3, p3):s1,s2表示原始的字符数组 s3表示交错出的字符数组。 p1,p2,p3分别表示当前指向各自字符数组的下标。 base case是p3s3.length, 即字符数组s3被s1,s2各自分配的字符匹配完了。 在保证字符数组不越界的情况 如果s1,s2当前的字符同时匹配 通过或逻辑就成功分类讨论了。 取结果的并集。
下面解法会超时 但已经能过部分样例。 子问题重叠。
class Solution {public boolean isInterleave(String str1, String str2, String str3) {char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();char[] s3 str3.toCharArray();if(s1.length s2.length ! s3.length){return false;}return f(s1,0,s2,0,s3,0);}public static boolean f(char[] s1,int p1, char[]s2, int p2, char[] s3, int p3){if(p3 s3.length){return true;}//选择方案boolean ans false;if(p1 s1.length s1[p1] s3[p3]){ans | f(s1,p11,s2,p2,s3,p31);}if(p2 s2.length s2[p2] s3[p3]){ans | f(s1,p1,s2,p21,s3,p31);}return ans;}
}接下用dp表优化 挂个bool dp表 但是需要注意Java中boolean数组元素默认值是false. false无法区分这个元素是否被处理过还是这个方案不行。 因此要改进成Boolean数组, 用null区分即可, 处理过的结果要么是false或者true。 为什么下面不是改进成三维动态规划 因为最终情况要么能达到s3.length或者不能 可以直接确定答案 因此给dp表再加一维没有必要 二维dp表就可以完美解决了.
下面代码提交可以打败100%。
class Solution {public boolean isInterleave(String str1, String str2, String str3) {char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();char[] s3 str3.toCharArray();if (s1.length s2.length ! s3.length) {return false;}// 创建dp和visited数组Boolean[][] dp new Boolean[s1.length 1][s2.length 1];return f(s1, 0, s2, 0, s3, 0, dp);}private boolean f(char[] s1, int p1, char[] s2, int p2, char[] s3, int p3, Boolean[][] dp) {if (p3 s3.length) { // 如果s3遍历完返回truereturn true;}if (dp[p1][p2] ! null) { // 如果已经计算过直接返回结果return dp[p1][p2];}boolean ans false;// 尝试从s1取字符匹配if (p1 s1.length s1[p1] s3[p3]) {ans f(s1, p1 1, s2, p2, s3, p3 1, dp);}// 如果从s1失败尝试从s2取字符匹配if (!ans p2 s2.length s2[p2] s3[p3]) {ans f(s1, p1, s2, p2 1, s3, p3 1, dp);}// 记录状态dp[p1][p2] Boolean.valueOf(ans);return ans;}
} 方法2直接入手转移方程
dp[i][j], 这里严格定义dp表的含义 取字符数组s1的前i个 另取字符数组的前j个 能否组成s3数组的前ij个。
s1的[0…i-1]区间 s2的[0…j-1]区间 能否组成s3[0…ij-1]的区间。
如果s1[i-1]s3[ij-1], 那么结果依赖dp[i-1][j]。如果s2[j-1]s3[ij-1], 那么结果依赖dp[i][j-1]。如果都不满足 那么false, 不能交错组成。12情况任意一项成立 那么结果为true。
dp表的简单部分如何填 思考dp表的定义。 dp[0][0] true, 显然。 根据前面的定义 取字符数组s1的0个 另取字符数组的0个 能否组成s3数组的0个。必然可以。
//单独取一个字符数组进行匹配s3前面几个字符for(int i1;in;i){if(s1[i-1] ! s3[i-1]){break;}dp[i][0] true;}for(int j1;jm;j){if(s2[j-1] ! s3[j-1]){break;}dp[0][j] true;}class Solution {public boolean isInterleave(String str1, String str2, String str3) {if(str1.length() str2.length() ! str3.length() ){return false;}char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();char[] s3 str3.toCharArray();int n s1.length;int m s2.length;boolean[][] dp new boolean[n1][m1];dp[0][0] true;for(int i1;in;i){if(s1[i-1] ! s3[i-1]){break;}dp[i][0] true;}for(int j1;jm;j){if(s2[j-1] ! s3[j-1]){break;}dp[0][j] true;}for(int i1;in;i){for(int j1;jm;j){dp[i][j] (s1[i-1]s3[ij-1]dp[i-1][j])||(s2[j-1]s3[ij-1]dp[i][j-1]);}}return dp[n][m];}
} 方法3空间压缩位置依赖
由于每一行都跟上一行的状态有关 因此仅需一个一维数组和少数变量就可以滚动更新 减少内存使用。
从第0行开始自上向下自左向右进行滚动 压缩成一维dp表。
class Solution {public boolean isInterleave(String str1, String str2, String str3) {if (str1.length() str2.length() ! str3.length()) {return false;}char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();char[] s3 str3.toCharArray();int n s1.length;int m s2.length;boolean[] dp new boolean[m 1];// 初始化第一列的状态表示 s1 完全匹配 s3 的情况dp[0] true;for (int j 1; j m; j) {if (s2[j - 1] ! s3[j - 1]) {break; // 如果 s2[j-1] 和 s3[j-1] 不相等后续就不需要继续检查了}dp[j] true; // 初始化 dp[j] 的状态}// 处理 s1 和 s2 的交错匹配for (int i 1; i n; i) {dp[0] (s1[i - 1] s3[i - 1]) dp[0]; // 更新 dp[0] 状态for (int j 1; j m; j) {dp[j] (s1[i - 1] s3[i j - 1] dp[j]) || (s2[j - 1] s3[i j - 1] dp[j - 1]);}}return dp[m];}
}
结语
动态规划的题解好难写…. 空间压缩不会二维dp表真不好分析。
