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.
1 public class Solution { 2 /** 3 * @param s1 A string 4 * @param s2 Another string 5 * @return whether s2 is a scrambled string of s1 6 */ 7 public boolean isScramble(String s1, String s2) { 8 if (s1.length() != s2.length()) return false; 9 10 if (s1.equals(s2)) return true;11 12 if (!isValid(s1, s2)) {13 return false;14 }15 16 for (int i = 1; i < s1.length(); i++) {17 String s11 = s1.substring(0, i);18 String s12 = s1.substring(i);19 20 String s21 = s2.substring(0, i);21 String s22 = s2.substring(i);22 23 String s23 = s2.substring(0, s2.length() - i);24 String s24 = s2.substring(s2.length() - i);25 26 if (isScramble(s11, s21) && isScramble(s12, s22) || isScramble(s11, s24) && isScramble(s12, s23)) {27 return true;28 }29 }30 return false;31 }32 33 private boolean isValid(String s1, String s2) {34 char[] arr1 = s1.toCharArray();35 char[] arr2 = s2.toCharArray();36 Arrays.sort(arr1);37 Arrays.sort(arr2);38 if (!(new String(arr1)).equals(new String(arr2))) {39 return false;40 }41 return true;42 }43 }