【二维动态规划：交错字符串】

介绍

编程语言：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(p1<s1.length&&p2<s2.length){if(s1[p1]==s3[i]){p1++;i++;}else if(s2[p2]==s3[i]){p2++;i++;}else{return false;}}while(p1<s1.length){if(s1[p1++]!=s3[i++]){return false;}}while(p2<s2.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是p3==s3.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,p1+1,s2,p2,s3,p3+1);}if(p2 < s2.length && s2[p2] == s3[p3]){ans |= f(s1,p1,s2,p2+1,s3,p3+1);}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数组的前i+j个。

s1的[0…i-1]区间， s2的[0…j-1]区间， 能否组成s3[0…i+j-1]的区间。

1. 如果s1[i-1]==s3[i+j-1], 那么结果依赖dp[i-1][j]。
2. 如果s2[j-1]==s3[i+j-1], 那么结果依赖dp[i][j-1]。
3. 如果都不满足， 那么false, 不能交错组成。1，2情况任意一项成立， 那么结果为true。

dp表的简单部分如何填？
思考dp表的定义。
dp[0][0] = = true, 显然。 根据前面的定义， 取字符数组s1的0个， 另取字符数组的0个， 能否组成s3数组的0个。必然可以。

//单独取一个字符数组进行匹配s3前面几个字符for(int i=1;i<=n;i++){if(s1[i-1] != s3[i-1]){break;}dp[i][0] = true;}for(int j=1;j<=m;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[n+1][m+1];dp[0][0] = true;for(int i=1;i<=n;i++){if(s1[i-1] != s3[i-1]){break;}dp[i][0] = true;}for(int j=1;j<=m;j++){if(s2[j-1] != s3[j-1]){break;}dp[0][j] = true;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j] = (s1[i-1]==s3[i+j-1]&&dp[i-1][j])||(s2[j-1]==s3[i+j-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表真不好分析。