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<len; i++){
for(int j=0; j<len; j++){ // 如果字符串总长度为1，则取决于唯一的字符是否想到
canT[0][i][j] = c1[i] == c2[j];
}
}
for(int k=2; k<=len; k++){ // 子串的长度
for(int i=len-k; 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
// Memo for dp.
private Map<String, Boolean> dp = new HashMap<String, Boolean>();
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