Scramble String leetcode

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.

state:dp[i][j][len] 

这道题我们维护一个三维动态规划量dp[i][j][len] 其中i为s1的起始位置, j为s2的起始位置, len为长度

dp[i][j][len]表示s1从i位到i+ len位置 与 s2从j位到j+len位是否是Scramble String 

初始化:dp[i][j][1] = s1.charAt(i) == s2.charAt(j) 如果s1的i位与s2的j位字母相同 则为true

function: dp[i][j][len] = dp[i][j][l] && dp[i + l][j + l][len - l] || dp[i][j + len - l][l] && dp[i + l] [j][len - l] 

有两种情况为true:

1. 存在着一点k (0 < k < len)使得s1.substring(i, i+k) 和 s2.substring(j, j+k) 为Scramble String  s1.substing(i + k, i +len), s2.substring(j +k, j + len)为Scramble String 就是说s1左边的substring和s2左边的substirng s1右边的substring 和s2右边的substring  为Scramble String  

2. 存在着一点k (0 < k < len)使得s1.substring(i, i+k) 和 s2.substring(j +len - k, j + len)  为Scramble String  s1.substing(i+k, i +len), s2.substring(j, j + len - k)为Scramble String 就是说s1左边的substring和s2右边的substirng s1右边的substring 和s2左边的substring  为Scramble String 

return: dp[0][0][n]

时间O(n^4) 空间 O(n^3)

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int n = s1.length();
        boolean[][][] dp = new boolean[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                for (int len = 1; len <= n - Math.max(i, j); len++) {
                    for (int l = 1; l < len; l++) {
                        if (dp[i][j][l] && dp[i + l][j + l][len - l] || dp[i][j + len - l][l] && dp[i + l] [j][len - l]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                    // }
                }
            }
        }
        return dp[0][0][n];
    }
}