package question;

import java.util.Arrays;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question87 {
 public static void main(String[] args) {
 System.out.println(new Question87().isScramble("abb",
 "bba"));
 }

 public boolean isScramble(String s1, String s2) {
 if (s1.equals(s2)) return true;
 int n = s1.length();
 boolean[][][] dp = new boolean[n + 1][n][n];
 for (boolean[] booleans : dp[0]) {
 Arrays.fill(booleans, true);
 }
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
 }
 }
 for (int k = 2; k <= n; k++) {
 for (int i = 0; i + k <= n; i++) {
 for (int j = 0; j + k <= n; j++) {
 for (int l = 1; l < k; l++) {
 dp[k][i][j] = (dp[k][i][j] || (dp[l][i][j] && dp[k - l][i + l][j + l]) || (dp[l][i][j + k - l] && dp[k - l][i + l][j]));
 }
 }
 }
 }
 return dp[n][0][0];
 }
}