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.

Analsysi:

We observe that if s1[0..i] and s2[0...i] are scramble strings, then there must have a k (0<=k<i) so that

1. s1[0..k] and s2[0...k] are scarable && s1[k+1...i] and s2[k+1...i] are scramble.

2. OR s1[0...k] and s2[i-k...i] are scramble && s1[k...i] and s2[0...i+k] are scramble.

We then define the define the state d[k][i][j] as whether the string s1[i...i+k] and s2[j...j+k] are scramble. We then have the formula:

d[k][i][j] = true; if for any l that 1<=l<=k-1, we have:  1. d[l][i][j] && d[k-l][i+l][j+l]  ||  2. d[l][i][j+k-l] && d[k-l][i+l][j].

Otherweise d[k][i][j] = false;

Solution:

 1 public class Solution { 2     public boolean isScramble(String s1, String s2) { 3         if (s1.length()!=s2.length()) return false; 4         int len = s1.length(); 5         if (len==0) return true; 6  7         boolean[][][] d = new boolean[len+1][len][len]; 8         for (int i=0;i<len;i++) 9             for (int j=0;j<len;j++)10                 if (s1.charAt(i)==s2.charAt(j))11                     d[1][i][j]=true;12                 else d[1][i][j]=false;13 14         for (int k=2;k<=len;k++)15             for (int i=0;i<=len-k;i++)16                 for (int j=0;j<=len-k;j++)17                     for (int l=1;l<=(k-1);l++){18                         d[k][i][j]=false;19                         if (d[l][i][j] && d[k-l][i+l][j+l]){20                             d[k][i][j]=true;21                             break;22                         } else if (d[l][i][j+k-l] && d[k-l][i+l][j]){23                             d[k][i][j]=true;24                             break;25                         }26                     }27 28          return d[len][0][0];29     }30 }

Leetcode-Scramble String