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.

Solution I: Recursion

public static boolean isScramble(String s1, String s2) { if(s1.length() != s2.length()){ return false; } if(s1.length()==1 && s2.length()==1){ return s1.charAt(0) == s2.charAt(0); } // 排序后可以通过 char[] s1ch = s1.toCharArray(); char[] s2ch = s2.toCharArray(); Arrays.sort(s1ch); Arrays.sort(s2ch); if(!new String(s1ch).equals(new String(s2ch))){ return false; } for(int i=1; i<s1.length(); i++){ // 至少分出一个字符出来 String s11 = s1.substring(0, i); String s12 = s1.substring(i); String s21 = s2.substring(0, i); String s22 = s2.substring(i); // System.out.println(s1 + "-" + s2 + ": "+ s11 + ", " + s12 + ", " + s21 + ", " + s22); // 检测前半部是否匹配 if(isScramble(s11, s21) && isScramble(s12, s22)){ return true; } // 前半部不匹配，检测后半部是否匹配 s21 = s2.substring(0, s2.length()-i); s22 = s2.substring(s2.length()-i); if(isScramble(s11, s22) && isScramble(s12, s21)){ return true; } } return false; }

Solution II: Recursion with prune

这里的剪枝条件可以简单设为，所有字符的ASCII的值之和必须相等，这是成为scramble的一个充分条件

public boolean isScramble2(String s1, String s2) { // Two quick recursion exits. if (s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; // Prune candidates here to reduce candidate check times. int sum = 0; for (int i = 0; i < s1.length(); i++) { sum += s1.charAt(i) - 'a'; sum -= s2.charAt(i) - 'a'; } if (sum != 0) return false; // Partition and match recursively. for (int i = 1; i < s1.length(); ++i) { for (int j = 1; j < s2.length(); ++j) { // i and j are the partition indexes. String s1_left = s1.substring(0, i); String s1_right = s1.substring(i); String s2_left = s2.substring(0, j); String s2_right = s2.substring(j); if (isScramble2(s1_left, s2_right) && isScramble2(s1_right, s2_left) || isScramble2(s1_left, s2_left) && isScramble2(s1_right, s2_right)) { return true; } } } return false; }

Solution III: DP 3D

public static boolean isScrambleDP(String s1, String s2) { int len = s1.length(); if(len != s2.length()){ return false; } if(len == 0){ return true; } char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); // canTransform 第一维为子串的长度delta，第二维为s1的起始索引，第三维为s2的起始索引 // canTransform[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]变化得来。 boolean[][][] canT = new boolean[len][len][len]; for(int i=0; i=0; i--){ // s1[i...i+k] for(int j=len-k; j>=0; j--){ // s2[j...j+k] boolean canTransform = false; for(int m=1; m<k; m++){ // 尝试以m为长度分割子串 // canT[k][i][j] canTransform = (canT[m-1][i][j] && canT[k-m-1][i+m][j+m]) || // 前前后后匹配 (canT[m-1][i][j+k-m] && canT[k-m-1][i+m][j]); // 前后后前匹配 if(canTransform){ break; } } canT[k-1][i][j] = canTransform; } } } return canT[len-1][0][0]; }

Solution IV: use Map

不过以上解法非常的麻烦，而且其实这种3维的DP表里仍然会存储冗余的状态。自己想出了一种非常规的DP求解方法，发现可以用一个哈希表代替3维的DP表，减少对冗余状态的存储。另外这里的DP其实可以跟递归思路一样，自顶向下，而非所谓真正的自底向上的DP。

这里记录子问题求解结果的数据结构我用Map，前面其实偷了一下懒，理论上应该是类似于Pair一样的东西，就是任意两个字符串看成一个pair，然后记录是否为scramble的结果。但是如果真的手动写个类，还有覆盖equals方法，太麻烦了，于是这里偷懒一下，把Pair的形式替换成s1@s2，记成一种特殊字符串。 另外，这里提供了几个快速的递归出口，一个是如果两个字符串长度不相等，可以立刻返回false。另一个是如果两个字符串内容相等，则可以立刻返回true。

// Memo for dp. private Map dp = new HashMap(); public boolean isScramble(String s1, String s2) { String key = s1 + "@" + s2; if (dp.containsKey(key)) { return dp.get(key); } // Two quick recursion exits. if (s1.length() != s2.length()) { dp.put(key, false); return false; } if (s1.equals(s2)) { dp.put(key, true); return true; } // Partition and match recursively. for (int i = 1; i < s1.length(); ++i) { for (int j = 1; j < s2.length(); ++j) { // i and j are the partition indexes. String s1_left = s1.substring(0, i); String s1_right = s1.substring(i); String s2_left = s2.substring(0, j); String s2_right = s2.substring(j); if (isScramble2(s1_left, s2_right) && isScramble2(s1_right, s2_left) || isScramble2(s1_left, s2_left) && isScramble2(s1_right, s2_right)) { return true; } } } dp.put(key, false); return false; }

REF:

http://blog.csdn.net/fightforyourdream/article/details/17707187

http://blog.csdn.net/whuwangyi/article/details/14105063