3. 递归加Memory
我们在递归中加上记忆矩阵,也可以减少重复运算,但是我们现在就改一下之前递归的结构以方便加上记忆矩阵,我们用index1记忆S1起始地址,index2记忆S2起始地址,len 表示字符串的长度。这样我们可以用一个三维数组来记录计算过的值,同样可以通过leetcode的检查。这个三维数组一个是N^3的复杂度,在每一个递归中,要从1-len地计算一次所有的子串,所以一共的复杂度是N^4
1 // Solution 3: The recursion version with memory. 2 // 閫氳繃璁板繂鐭╅樀鏉ュ噺灏戣绠楅噺 3 public static boolean isScramble3(String s1, String s2) { 4 if (s1 == null || s2 == null) { 5 return false; 6 } 7 8 int len1 = s1.length(); 9 int len2 = s2.length(); 10 11 // the two strings should be the same length. 12 if (len1 != len2) { 13 return false; 14 } 15 16 int[][][] mem = new int[len1][len1][len1]; 17 for (int i = 0; i) { 18 for (int j = 0; j ) { 19 for (int k = 0; k ) { 20 // -1 means unseted. 21 mem[i][j][k] = -1; 22 } 23 } 24 } 25 26 return recMem(s1, 0, s2, 0, len1, mem); 27 } 28 29 // Solution 3: The recursion version with memory. 30 // 閫氳繃璁板繂鐭╅樀鏉ュ噺灏戣绠楅噺 31 public static boolean recMem(String s1, int index1, String s2, int index2, 32 int len, int[][][] mem) { 33 // the base case. 34 if (len == 1) { 35 return s1.charAt(index1) == s2.charAt(index2); 36 } 37 38 // LEN: 1 - totalLen-1 39 int ret = mem[index1][index2][len - 1]; 40 if (ret != -1) { 41 return ret == 1 ? true : false; 42 } 43 44 // 鍒濆鍖栦负false 45 ret = 0; 46 47 // 鍒掑垎2涓瓧绗︿覆. i means the length of the left side in S1 48 for (int i = 1; i ) { 49 // we have two situation; 50 // the left-left right-right & left-right right-left 51 if (recMem(s1, index1, s2, index2, i, mem) 52 && recMem(s1, index1 + i, s2, index2 + i, len - i, mem)) { 53 ret = 1; 54 break; 55 } 56 57 if (recMem(s1, index1, s2, index2 + len - i, i, mem) 58 && recMem(s1, index1 + i, s2, index2, len - i, mem)) { 59 ret = 1; 60 break; 61 } 62 } 63 64 mem[index1][index2][len - 1] = ret; 65 return ret == 1 ? true : false; 66 }
4. 动态规划。
其实如果写出了3,动态规划也就好写了。
三维动态规划题目:
我们提出维护量res[i][j][n],其中i是s1的起始字符,j是s2的起始字符,而n是当前的字符串长度,res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。
有了维护量我们接下来看看递推式,也就是怎么根据历史信息来得到res[i][j][len]。判断这个是不是满足,其实我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分,然后分两种情况:第一种是左边和s2[j...j+len-1]左边部分是不是scramble,以及右边和s2[j...j+len-1]右边部分是不是scramble;第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble,以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立,说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的,因为长度小于n的所有情况我们都在前面求解过了(也就是长度是最外层循环)。
上面说的是劈一刀的情况,对于s1[i...i+len-1]我们有len-1种劈法,在这些劈法中只要有一种成立,那么两个串就是scramble的。
总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k
如此总时间复杂度因为是三维动态规划,需要三层循环,加上每一步需要线行时间求解递推式,所以是O(n^4)。虽然已经比较高了,但是至少不是指数量级的,动态规划还是相当有用的,空间复杂度是O(n^3)。代码如下:
注:事实上这里最大的难点,是你怎么安排这三个循环。仔细看一下,计算len对应的解时,要用到一堆len-1的解。所以我们应该len 从0到1地这要子计算(三维啊都没办法通过画图来推导动态规划的递增关系了!)
1 /* 2 * Solution 4: The DP Version. 3 */ 4 public static boolean isScramble4(String s1, String s2) { 5 if (s1 == null || s2 == null) { 6 return false; 7 } 8 9 int len1 = s1.length(); 10 int len2 = s2.length(); 11 12 // the two strings should be the same length. 13 if (len1 != len2) { 14 return false; 15 } 16 17 /* 18 * i: The index of string 1. j: The index of string 2. k: The length of 19 * the two string. 1 ~ len1 20 * 21 * D[i][j][k] = 22 */ 23 boolean[][][] D = new boolean[len1][len1][len1 + 1]; 24 for (int subLen = 1; subLen <= len1; subLen++) { 25 for (int i1 = 0; i1 <= len1 - subLen; i1++) { 26 for (int i2 = 0; i2 <= len1 - subLen; i2++) { 27 if (subLen == 1) { 28 D[i1][i2][subLen] = s1.charAt(i1) == s2.charAt(i2); 29 continue; 30 } 31 32 D[i1][i2][subLen] = false; 33 for (int l = 1; l) { 34 if (D[i1][i2][l] && D[i1 + l][i2 + l][subLen - l] 35 || D[i1][i2 + subLen - l][l] && D[i1 + l][i2][subLen - l] 36 ) { 37 D[i1][i2][subLen] = true; 38 break; 39 } 40 } 41 } 42 } 43 } 44 45 return D[0][0][len1]; 46 } 47 48 /* 49 * Solution 4: The DP Version. REDO 50 */ 51 public static boolean isScramble(String s1, String s2) { 52 if (s1 == null || s2 == null) { 53 return false; 54 } 55 56 int len = s1.length(); 57 58 if (s2.length() != len) { 59 return false; 60 } 61 62 boolean[][][] D = new boolean[len][len][len + 1]; 63 64 // D[i][j][k] = D[i][] 65 for (int k = 1; k <= len; k++) { 66 // 注意这里的边界选取。 如果选的不对,就会发生越界的情况.. orz.. 67 // attention: should use "<=" 68 for (int i = 0; i <= len - k; i++) { 69 for (int j = 0; j <= len - k; j++) { 70 if (k == 1) { 71 D[i][j][k] = s1.charAt(i) == s2.charAt(j); 72 continue; 73 } 74 75 D[i][j][k] = false; 76 for (int l = 1; l <= k - 1; l++) { 77 if (D[i][j][l] && D[i + l][j + l][k - l] 78 || D[i][j + k - l][l] && D[i + l][j][k - l] ) { 79 D[i][j][k] = true; 80 break; 81 } 82 } 83 } 84 } 85 } 86 87 return D[0][0][len]; 88 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/9241a5148ba94d79c7dfcb3dbbbd3ad5474bdcf1/dp/IsScramble.java