## 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.

### 分析

f[n][i][j]} =  (f[k][i][j] && f[n-k][i+k][j+k])
|| (f[k][i][j+n-k] && f[n-k][i+k][j])


### 递归

// Scramble String
// 递归，会超时，仅用来帮助理解
// 时间复杂度O(n^6)，空间复杂度O(1)
public class Solution {
public boolean isScramble(String s1, String s2) {
return isScramble(s1, 0, s1.length(), s2, 0);
}
private static boolean isScramble(String s1, int begin1, int end1,
String s2, int begin2) {
final int length = end1 - begin1;
final int end2 = begin2 + length;

if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);

for (int i = 1; i < length; ++i)
if ((isScramble(s1, begin1, begin1 + i, s2, begin2)
&& isScramble(s1, begin1 + i, end1, s2, begin2 + i))
|| (isScramble(s1, begin1, begin1 + i, s2, end2 - i)
&& isScramble(s1, begin1 + i, end1, s2, begin2)))
return true;

return false;
}
}

### 动规

// Scramble String
// 动规，时间复杂度O(n^3)，空间复杂度O(n^3)
public class Solution {
public boolean isScramble(String s1, String s2) {
final int N = s1.length();
if (N != s2.length()) return false;

// f[n][i][j]，表示长度为n，起点为s1[i]和
// 起点为s2[j]两个字符串是否互为scramble
boolean[][][] f = new boolean[N+1][N][N];

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[1][i][j] = s1.charAt(i) == s2.charAt(j);

for (int n = 1; n 

### 递归+剪枝

// Scramble String
// 递归+剪枝
// 时间复杂度O(n^6)，空间复杂度O(1)
public class Solution {
public boolean isScramble(String s1, String s2) {
return isScramble(s1, 0, s1.length(), s2, 0);
}
private static boolean isScramble(String s1, int begin1, int end1,
String s2, int begin2) {
final int length = end1 - begin1;
final int end2 = begin2 + length;
if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);

// 剪枝，提前返回
int[] A = new int[26]; // 每个字符的计数器
for(int i = 0; i < length; i++) A[s1.charAt(begin1+i)-'a']++;
for(int i = 0; i < length; i++) A[s2.charAt(begin2+i)-'a']--;
for(int i = 0; i < 26; i++) if (A[i] != 0) return false;

for (int i = 1; i < length; ++i)
if ((isScramble(s1, begin1, begin1 + i, s2, begin2)
&& isScramble(s1, begin1 + i, end1, s2, begin2 + i))
|| (isScramble(s1, begin1, begin1 + i, s2, end2 - i)
&& isScramble(s1, begin1 + i, end1, s2, begin2)))
return true;

return false;
}
}

### 备忘录法

// Scramble String
// 递归+map做cache
// 时间复杂度O(n^3)，空间复杂度O(n^3), TLE
public class Solution {
public boolean isScramble(String s1, String s2) {
cache.clear();
return isScramble(s1, 0, s1.length(), s2, 0);
}

final private HashMap cache = new HashMap<>();

private boolean isScramble(String s1, int begin1, int end1,
String s2, int begin2) {
final int length = end1 - begin1;
final int end2 = begin2 + length;

if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2);

for (int i = 1; i < length; ++i)
if ((getOrUpdate(s1, begin1, begin1 + i, s2, begin2)
&& getOrUpdate(s1, begin1 + i, end1, s2, begin2 + i))
|| (getOrUpdate(s1, begin1, begin1 + i, s2, end2 - i)
&& getOrUpdate(s1, begin1 + i, end1, s2, begin2)))
return true;

return false;
}

boolean getOrUpdate(String s1, int begin1, int end1,
String s2, int begin2) {
Triple key = new Triple(begin1, end1, begin2);
if (!cache.containsKey(key)) {
boolean result = isScramble(s1, begin1, end1, s2, begin2);
cache.put(key, result);
return result;
} else {
return cache.get(key);
}
}
static class Triple {
private int i;
private int j;
private int k;

public Triple(int i, int j, int k) {
this.i = i;
this.j = j;
this.k = k;
}
@Override
public int hashCode() {
int hash = 0;
hash = i * 31 + j;
hash = hash * 31 * k;
return hash;
}
@Override
public boolean equals(Object other) {
if (this == other) return true;
if (this.hashCode() != other.hashCode()) return false;
if (!(other instanceof Triple)) return false;
Triple o = (Triple)other;
return this.i == o.i && this.j == o.j && this.k == o.k;
}
}
}