Scramble String

 1 public class Solution {
 2     public boolean isScramble(String s1, String s2) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         int n=s1.length();
 6         boolean[][][] dp=new boolean[n][n][n+1];
 7         
 8         for(int i=n-1; i>=0; i--)
 9             for(int j=n-1; j>=0; j--)
10                 for(int k=1; k<=n-Math.max(i,j);k++)
11                 {
12                     if(s1.substring(i,i+k).equals(s2.substring(j,j+k)))
13                         dp[i][j][k]=true;
14                     else
15                     {
16                         for(int l=1; l<k; l++)
17                         {
18                             if(dp[i][j][l] && dp[i+l][j+l][k-l] || dp[i][j+k-l][l] && dp[i+l][j][k-l])
19                             {
20                                 dp[i][j][k]=true;
21                                 break;
22                             }
23                         }
24                     }
25                 }
26         
27         return dp[0][0][n];
28     }
29 }