**Leetcode 87 Scramble String**

The problem description is as follow:

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.

**Recursive Approach**

Edit Scramble String on GitHub

The recursive approach is straight-forward. If `string s1`

is a scrambled string of `string s2`

, then there must exists a point that breaks `string s1`

into two parts `s11`

and `s12`

and a point that breaks `string s2`

into two parts `s21`

and `s22`

where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or 2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

In order to make the recursive method more efficient, we can add some simple validation. If `string s1`

is a scrambled string of `string s2`

, then they must share the same characters and have same length.

public class Solution { public boolean isScramble(String s1, String s2) { //Check lengths. if (s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; int L = s1.length(); //Check characters. int[] chars = new int[26]; for (int i = 0; i < L; i++) { chars[s1.charAt(i) - 'a']++; chars[s2.charAt(i) - 'a']--; } for (int i = 0; i < 26; i++) { if (chars[i] != 0) return false; } //More letters for (int i = 1; i < L; i++) { String s11 = s1.substring(0, i); String s12 = s1.substring(i, L); String s21 = s2.substring(0, i); String s22 = s2.substring(i, L); if (isScramble(s11, s21) && isScramble(s12, s22)) return true; s21 = s2.substring(0, L - i); s22 = s2.substring(L - i, L); if (isScramble(s11, s22) && isScramble(s12, s21)) return true; } return false; } }

**Dynamice Programming Approach**

Edit Scramble String on GitHub

Even if we add bunch of validations in the recursive approach, the time complexity is still not polynomial. In this case, we should seek a more efficient approach – DP approach.

I use a 3-D matrix `scramble[][][]`

to save all the states. Say `scramble[i][j][k]`

, `i`

stands for the starting index of `string s1`

and `j`

stands for the starting index of `string s2`

. `k`

stands for the length of current string. `scramble[i][j][k] = true`

means `s1.substring(i,i+k)`

and `s1.substring(j,j+k)`

are scrambled strings.

Now we only have to figure how to get the recursive formula for `scramble[i][j][k]`

from historical states we already got. As we discussed in the recursive approach, if `string s1`

is a scrambled string of `string s2`

, then there must exists a point that breaks `string s1`

into two parts `s11`

and `s12`

and a point that breaks `string s2`

into two parts `s21`

and `s22`

where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or 2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

Translating words into maths, we got:

For 1<=k<len, scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k])

Here comes the code:

public class Solution { public boolean isScramble(String s1, String s2) { //Check lengths. if (s1==null || s2==null || s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; int L = s1.length(); // scramble[i][j][k]=true means: s1.substring(i,i+k) and s2.substring(j,j+k) is scramble // Thus scramble[i][j][0] has no meaning, k start from 1 boolean[][][] scramble = new boolean[L][L][L+1]; // Initiate scramble[][][], note that in Java boolean's default value is false for (int i = 0; i < L; i++) { for (int j = 0; j < L; j++) if (s1.charAt(i) == s2.charAt(j)) scramble[i][j][1] = true; } for (int len = 2; len <= L; len++) { for (int i = 0;i < L - len + 1; i++) { for(int j = 0; j < L - len + 1; j++) { for(int k = 1; k < len; k++) { scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k]); } } } } return scramble[0][0][L]; } }

The time complexity is `O(n^4)`

and space complexity is `O(n^3)`

, all polynomial.

Now we are happy 😀