# 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 <= N; ++n) {            for (int i = 0; i + n <= N; ++i) {                for (int j = 0; j + n <= N; ++j) {                    for (int k = 1; k < n; ++k) {                        if ((f[k][i][j] && f[n - k][i + k][j + k]) ||                                (f[k][i][j + n - k] && f[n - k][i + k][j])) {                            f[n][i][j] = true;                            break;                        }                    }                }            }        }        return f[N][0][0];    }}

### 递归+剪枝​

// 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), TLEpublic class Solution {    public boolean isScramble(String s1, String s2) {        cache.clear();        return isScramble(s1, 0, s1.length(), s2, 0);    }    final private HashMap<Triple, Boolean> 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;        }    }}