Scramble String

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":

  1.     great
  2.    /    \
  3.   gr    eat
  4.  / \    /  \
  5. g   r  e   at
  6.            / \
  7.           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".

  1.     rgeat
  2.    /    \
  3.   rg    eat
  4.  / \    /  \
  5. r   g  e   at
  6.            / \
  7.           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".

  1.     rgtae
  2.    /    \
  3.   rg    tae
  4.  / \    /  \
  5. r   g  ta  e
  6.        / \
  7.       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.

Solution:

  1. public class Solution {
  2.   public boolean isScramble(String s1, String s2) {
  3.     if (!isAnagram(s1, s2))
  4.       return false;
  6.     if (s1.equals(s2))
  7.       return true;
  9.     int n = s1.length();
  11.     for (int i = 1; i < n; i++) {
  12.       String s11 = s1.substring(0, i);
  13.       String s12 = s1.substring(i, n);
  15.       String s21 = s2.substring(0, i);
  16.       String s22 = s2.substring(i, n);
  18.       if (isScramble(s11, s21) && isScramble(s12, s22))
  19.         return true;
  21.       s21 = s2.substring(0, n - i);
  22.       s22 = s2.substring(n - i, n);
  24.       if (isScramble(s11, s22) && isScramble(s12, s21))
  25.         return true;
  26.     }
  28.     return false;
  29.   }
  31.   boolean isAnagram(String s1, String s2) {
  32.     if (s1 == null || s2 == null || s1.length() != s2.length())
  33.       return false;
  35.     int[] arr = new int[26];
  37.     for (int i = 0; i < s1.length(); i++) {
  38.       arr[s1.charAt(i) - 'a']++;
  39.       arr[s2.charAt(i) - 'a']--;
  40.     }
  42.     for (int i = 0; i < 26; i++)
  43.       if (arr[i] != 0) return false;
  45.     return true;
  46.   }
  47. }