首页 > 代码库 > Leetcode:Interleaving String 解题报告
Leetcode:Interleaving String 解题报告
Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
题解：
到了HARD难度了，主页君好兴奋啊！啦啦啦
让我们来逐层分解DP吧！
其实DP的本质是Bottom -- UP的解决方法，先解决小的子问题，再一步一步解决大的问题，而递归是TOP-DOWN的解决方案。一开始就想最顶层的解决方案，通过递归来一层层分解成小的子问题。
今天我们来探讨一下本题的3种解法
1. Brute Force的递归解法。
index1, index2, index3分别代表s1,s2,s3三个字符串的起始地址（就是从哪里开始判断）
判断s1, s2, s3是否是Interleaving String 应该这样判断：
（1）. s3的首字母是来自s1吗？如果是，可以拆解为s1的 index1+1 与 s2 index2 与s3的Interleaving String子问题。
（2）. s3的首字母是来自s2吗？如果是，可以拆解为s2的 index2+1 与 s1 index1 与s3的Interleaving String子问题。
以上2个条件成立一个，表示我们的结果是成立。
Base Case:
如果index3 超过了s3的length，表示s3是空串，这时应返回TRUE
代码主页君没有写，可以参考第二个解法Brute Force 带Memory的解法，只需要把最后一个memory的参数拿走就可以了。
如果直接这样写Leetcode是time limited.
2. 递归加记忆矩阵的解法。
与1的思路完全一致，但是我们加一个二维矩阵来记录结果值，这样可以减少不必要的重复计算. 这样下来速度与DP会完全一致，也可以通过Leetcode的检查
1 // Solution1: Recursion with memory 2 public static boolean isInterleave1(String s1, String s2, String s3) { 3 if (s1 == null || s2 == null || s3 == null) { 4 return false; 5 } 6 7 int len1 = s1.length(); 8 int len2 = s2.length(); 9 int len3 = s3.length();10 11 // The length is not equal, just return false.12 if (len1 + len2 != len3) {13 return false;14 }15 16 int[][][] memory = new int[len1 + 1][len2 + 1][len3 + 1];17 for (int i = 0; i <= len1; i++) {18 for (int j = 0; j <= len2; j++) {19 for (int k = 0; k <= len3; k++) {20 memory[i][j][k] = -1;21 }22 }23 }24 25 return recMemory(s1, 0, s2, 0, s3, 0, memory);26 }27 28 public static boolean recMemory(String s1, int index1, String s2,29 int index2, String s3, int index3, int[][][] memory) {30 int len1 = s1.length();31 int len2 = s2.length();32 int len3 = s3.length();33 34 if (index3 == len3 && index1 == len1 && index2 == len2) {35 return true;36 }37 38 if (memory[index1][index2][index3] != -1) {39 return memory[index1][index2][index3] == 1;40 }41 42 // 第一个字符，有2种可能：来自s1, 或是来自s243 boolean ret = false;44 if (index1 < len1 && s1.charAt(index1) == s3.charAt(index3)) {45 ret = recMemory(s1, index1 + 1, s2, index2, s3, index3 + 1, memory);46 }47 48 // 如果不成功(首字母不来自于s1)，尝试另一种可能49 if (!ret && index2 < len2 && s2.charAt(index2) == s3.charAt(index3)) {50 ret = recMemory(s1, index1, s2, index2 + 1, s3, index3 + 1, memory);51 }52 53 memory[index1][index2][index3] = ret ? 1 : 0;54 return ret;55 }56 57 // Solution2: Recursion with memory58 // 思考了一下看了一下过去的代码，发现其实我们用不到三维数组，因为len1 + len2 = len3,59 // 所以第三维根本可以省略嘛60 public static boolean isInterleave2(String s1, String s2, String s3) {61 if (s1 == null || s2 == null || s3 == null) {62 return false;63 }64 65 int len1 = s1.length();66 int len2 = s2.length();67 int len3 = s3.length();68 69 // The length is not equal, just return false.70 if (len1 + len2 != len3) {71 return false;72 }73 74 int[][] memory = new int[len1 + 1][len2 + 1];75 for (int i = 0; i <= len1; i++) {76 for (int j = 0; j <= len2; j++) {77 memory[i][j] = -1;78 }79 }80 81 return recMemory2(s1, 0, s2, 0, s3, 0, memory);82 }
3. DP
D[i][j]: 定义为s1 (前i个字符) s2(前j个字符) s3(i+j 个字符) 是不是交叉字符
递推公式： (s1.i == s3.(i+j) && D[i-1][j]) || (s2.j == s3.(i+j) && D[i][j - 1])
分别从s1,s2两种可能性来匹配 ，两者有一个成立就行了。
s1 s3 首字母相同，继续查i -1 与 i + j -1 是否isInterleave1
s2 s3 首字母相同，继续查j -1 与 i + j -1 是否isInterleave1
初始化：D 0,0 就是true，因为都是空.
D[0][j] 就是判断一下str2与str3是不是尾字符相同，及D[0][j - 1]是不是true
D[i][0] 就是判断一下str1与str3是不是尾字符相同，及D[i - 1][0]是不是true
1 public class Solution { 2 public boolean isInterleave1(String s1, String s2, String s3) { 3 if (s1 == null || s2 == null || s3 == null) { 4 return false; 5 } 6 7 int len1 = s1.length(); 8 int len2 = s2.length(); 9 int len3 = s3.length();10 11 if (len1 + len2 != len3) {12 return false;13 }14 15 boolean[][] D = new boolean[len1 + 1][len2 + 1];16 17 for (int i = 0; i <= len1; i++) {18 for (int j = 0; j <= len2; j++) {19 D[i][j] = false;20 if (i == 0 && j == 0) {21 D[i][j] = true;22 } else if (i == 0) {23 D[i][j] = s2.charAt(j - 1) == s3.charAt(i + j - 1) && D[i][j - 1];24 } else if (j == 0) {25 D[i][j] = s1.charAt(i - 1) == s3.charAt(i + j - 1) && D[i - 1][j];26 } else {27 D[i][j] |= s2.charAt(j - 1) == s3.charAt(i + j - 1) && D[i][j - 1];28 D[i][j] |= s1.charAt(i - 1) == s3.charAt(i + j - 1) && D[i - 1][j];29 }30 }31 }32 33 return D[len1][len2];34 }35 36 public boolean isInterleave(String s1, String s2, String s3) {37 if (s1 == null || s2 == null || s3 == null) {38 return false;39 }40 41 int len1 = s1.length();42 int len2 = s2.length();43 int len3 = s3.length();44 45 if (len1 + len2 != len3) {46 return false;47 }48 49 boolean[][] D = new boolean[len1 + 1][len2 + 1];50 51 for (int i = 0; i <= len1; i++) {52 for (int j = 0; j <= len2; j++) {53 D[i][j] = false;54 if (i == 0 && j == 0) {55 D[i][j] = true;56 continue;57 }58 59 if (i != 0) {60 D[i][j] |= s1.charAt(i - 1) == s3.charAt(i + j - 1) && D[i - 1][j];61 }62 63 if (j != 0) {64 D[i][j] |= s2.charAt(j - 1) == s3.charAt(i + j - 1) && D[i][j - 1];65 }66 }67 }68 69 return D[len1][len2];70 }71 }
总结：同学在面试的时候，可以尝试写一个递归，然后根据当前问题的规模（比如我们现在是有2个字符串的不同长度组合），那么就可以创建一个二维矩阵来记录结果，加在递归上就能轻松减少复杂度。本题DP/带记忆的递归都是N^2的复杂度。
如果面试官进一步问，你可以根据前面递归的思路，推一个DP公式出来。这个多练几遍很快就会熟悉了。
最后上代码：
GitHub代码链接
Leetcode:Interleaving String 解题报告