首页 > 代码库 > 【leetcode刷题笔记】Scramble String
【leetcode刷题笔记】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.
题解：
第一个想法比较naive，想把s1和s2都按照字典序排列，然后看是否相同。提交后就发现下面的例子就能够证明这个算法的错误：
s1 = "abcd"s2 = "bdac"第二个想法是递归，如下图所示：
对于任意长度相等的s1和s2，都可以分解成上图两种情况，通过把s1和s2分成两部分，那么有两种情况s1和s2是scramble的，一种是两部分对应scramble；一种是两部分交换后scramble。这样就有了我们的递归解法。
但是仅仅是这种递归一定会超时，必须进行优化，有一下几点可以优化的地方：
- s1和s2长度必须相等；
- 长度相等且都为0，返回true；
- s1和s2完全相同返回true；
- s1和s2所包含的字母种类个数必须相同，即s1和s2按照字典序排序后必须相同；
通过以上的优化，递归方法就不会超时了。
代码如下：
1 public class Solution { 2 public boolean isScramble(String s1, String s2) { 3 int m = s1.length(); 4 int n = s2.length(); 5 6 if(m != n) 7 return false; 8 9 if(m == 0 || s1.equals(s2))10 return true;11 12 char[] chars1 = s1.toCharArray();13 char[] chars2 = s2.toCharArray();14 Arrays.sort(chars1);15 Arrays.sort(chars2);16 for(int i = 0;i < m;i++)17 if(chars1[i] != chars2[i])18 return false;19 20 for(int i = 1;i < m;i++){21 String s1left = s1.substring(0,i);22 String s1right = s1.substring(i);23 String s2left = s2.substring(0, i);24 String s2right = s2.substring(i);25 26 if(isScramble(s1left, s2left) && isScramble(s1right, s2right))27 return true;28 s2left = s2.substring(0,n-i);29 s2right = s2.substring(n-i);30 if(isScramble(s1left, s2right) && isScramble(s1right, s2left))31 return true;32 }33 34 return false;35 }36 }
上述方法耗时428ms。
第三个想法，动态规划。
递归之所以会超时，是因为做了许多重复的工作。用动态规划bottom-up的方法把这些重复的工作记录在表dp[][][]中，就可以省去重复计算的时间。
我们用dp[sublen][i][j]表示s1[i,i+sublen]和s2[j,j+sublen]是否是scramble的。那么有如下递推式：
dp[sublen][i][j] = (dp[k][i][j]&&dp[sublen-k][i+k][j+k]) || (dp[k][i][j+sublen-k] && dp[sublen-k][i+k][j]);
它对应了下图两种情况：
另外 dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
理解还算容易，写代码还是有难度的，一共四重循环：
第一重循环改变sublen的大小，从长度为2的子串一直增加至长度为n的串；
第二重循环改变i，即s1中游标的位置，从0~n-sublen;
第三重循环改变i，即s2中游标的位置，从0~n-sublen;
第四重循环枚举从i~i+sublen之间的每一中分割字符串的位置，考察这样分割是否能使得s1和s2对应的部分scramble得到，k从1~sublen-1；
代码如下：
1 public class Solution { 2 public boolean isScramble(String s1, String s2) { 3 if(s1.length() != s2.length()) 4 return false; 5 6 if(s1.length() == 0 && s2.length() == 0) 7 return true; 8 9 int n = s1.length();10 boolean[][][] dp = new boolean[n+1][n+1][n+1];11 for(int i = 0;i < n;i++){12 for(int j = 0;j < n;j++)13 dp[1][i][j] = s1.charAt(i) == s2.charAt(j); 14 }15 16 for(int sublen = 2;sublen <= n;sublen++){ 17 for(int i = 0;i <= n-sublen;i++){18 for(int j = 0;j <= n-sublen;j++){19 dp[sublen][i][j]= false; 20 for(int k = 1;k<sublen && dp[sublen][i][j]== false ;k++)21 dp[sublen][i][j] = (dp[k][i][j]&&dp[sublen-k][i+k][j+k]) || (dp[k][i][j+sublen-k] && dp[sublen-k][i+k][j]); 22 }23 }24 }25 return dp[n][0][0];26 }27 }