首页 > 代码库 > Leetcode:Scramble String 解题报告
Leetcode:Scramble String 解题报告
Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great / gr eat / \ / g r e at / a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat / rg eat / \ / r g e at / a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae / rg tae / \ / r g ta e / t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
解答：
1. Brute Force 递归。
基本的思想就是：在S1上找到一个切割点，左边长度为i, 右边长为len - i。 有2种情况表明它们是IsScramble
(1). S1的左边和S2的左边是IsScramble， S1的右边和S2的右边是IsScramble
(2). S1的左边和S2的右边是IsScramble， S1的右边和S2的左边是IsScramble （实际上是交换了S1的左右子树）
而i的取值可以是1 ~ len-1。 基于这个思想，我们可以写出以下的递归Brute Force 解：
引自stellari对复杂度的解释：
看了你的不少文章，感觉收获良多！只是有点小问题想请教：按照我的理解，那个递归算法在最差情况下应该是O(3^n)，而非O(n^2)。理由是：假设函数运行时间为f(n)，那么由于在每次函数调用中都要考虑1~n之间的所有长度，并且正反都要检查，所以有
f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)]. 易推得f(n+1) = 3(fn), 故f(n) = O(3^n)。当然这是最差情况下的时间复杂度。那么你提到的O(n^2)，是否是通过其他数学方法得到的更tight的上限？欢迎探讨！
这一个解是不能通过LeetCode的检查的，复杂度是 3^N
1 public static boolean isScramble1(String s1, String s2) { 2 if (s1 == null || s2 == null) { 3 return false; 4 } 5 6 int len1 = s1.length(); 7 int len2 = s2.length(); 8 9 // the two strings should be the same length.10 if (len1 != len2) {11 return false;12 }13 14 return rec(s1, s2);15 }16 17 // Solution 1: The recursion version.18 public static boolean rec1(String s1, String s2) {19 int len = s1.length();20 21 // the base case.22 if (len == 1) {23 return s1.equals(s2);24 }25 26 // 鍒掑垎2涓瓧绗︿覆27 for (int i = 1; i < len; i++) {28 // we have two situation;29 // the left-left right-right & left-right right-left30 if (rec1(s1.substring(0, i), s2.substring(0, i))31 && rec1(s1.substring(i, len), s2.substring(i, len))) {32 return true;33 }34 35 if (rec1(s1.substring(0, i), s2.substring(len - i, len))36 && rec1(s1.substring(i, len), s2.substring(0, len - i))) {37 return true;38 }39 }40 41 return false;42 }
2. 递归加剪枝
感谢unieagle的提示，我们可以在递归中加适当的剪枝，也就是说在进入递归前，先把2个字符串排序，再比较，如果不相同，则直接退出掉。这样也能有效地减少复杂度，具体多少算不清。但能通过leetcode的检查。
1 // Solution 2: The recursion version with sorting. 2 // 鎺掑簭涔嬪悗鐨勫壀鏋濆彲浠ラ?杩嘗eetCode鐨勬鏌? 3 public static boolean rec(String s1, String s2) { 4 int len = s1.length(); 5 6 // the base case. 7 if (len == 1) { 8 return s1.equals(s2); 9 }10 11 // sort to speed up.12 char[] s1ch = s1.toCharArray();13 Arrays.sort(s1ch);14 String s1Sort = new String(s1ch);15 16 char[] s2ch = s2.toCharArray();17 Arrays.sort(s2ch);18 String s2Sort = new String(s2ch);19 20 if (!s1Sort.equals(s2Sort)) {21 return false;22 }23 24 // 鍒掑垎2涓瓧绗︿覆25 for (int i = 1; i < len; i++) {26 // we have two situation;27 // the left-left right-right & left-right right-left28 if (rec(s1.substring(0, i), s2.substring(0, i))29 && rec(s1.substring(i, len), s2.substring(i, len))) {30 return true;31 }32 33 if (rec(s1.substring(0, i), s2.substring(len - i, len))34 && rec(s1.substring(i, len), s2.substring(0, len - i))) {35 return true;36 }37 }38 39 return false;40 }
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 < len1; i++) {18 for (int j = 0; j < len1; j++) {19 for (int k = 0; k < len1; 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-139 int ret = mem[index1][index2][len - 1];40 if (ret != -1) {41 return ret == 1 ? true : false;42 }43 44 // 鍒濆鍖栦负false45 ret = 0;46 47 // 鍒掑垎2涓瓧绗︿覆. i means the length of the left side in S148 for (int i = 1; i < len; i++) {49 // we have two situation;50 // the left-left right-right & left-right right-left51 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 of19 * the two string. 1 ~ len120 * 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 < subLen; 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. REDO50 */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 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/9241a5148ba94d79c7dfcb3dbbbd3ad5474bdcf1/dp/IsScramble.java
Leetcode:Scramble String 解题报告