87. Scramble String Leetcode Java

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.

Solution:

This problem is an advanced dynamic programming problem, first of all, the scrambled string must have the same length with the original one. Assume both s1 and s2 have the length of L, the left part of s1 with length k: s1[0,k] is scrambled string of right part of s2[L-k,L] and also s1[L-k,L] is scrambled string of s2[0,k], undoubtedly, s1 is scrambled string of s2, because this is just caused by swap 0->k with L-k->L. And another scenario can also leads to the same conclusion is that, s1[0,k] is scrambled string of s2[0,k] and s1[L-k,L] is scrambled string of s2[L-k,L]. Obviously, k can be any Integer between 0 and L, so our DP array will be a 3-d array, which store the information that if a substring with length l starting from i in s1 is scrambled string of a substring with same length starting from index j in s2.  And the recursion equation will be dp[i][j][l]=(dp[i][j][k]&& dp[i+k][j+k][l-k]) || (dp[i][j+l-k][k] && dp[i+k][j][l-k]) if any k can make dp[i][j][l] true, it will be true.

Time complexity: O(n^4)

 public boolean isScramble(String s1, String s2) {  
    if(s1==null || s2==null || s1.length()!=s2.length()) return false;  
    if(s1.length()==0) return true;  
    int l=s1.length();  
    boolean[][][] res= new boolean[l][l][l];  
    for(int i=0;i<l;i++){  
      for(int j=0;j<l;j++){  
       res[i][j][0]=(s1.charAt(i)==s2.charAt(j));  
      }  
    }  
    for(int m=1;m<l;m++){  
      for(int i=0;i<l-m;i++){  
        for(int j=0; j<l-m;j++){  
          for(int k=0;k<m;k++){  
            if((res[i][j][k] && res[i+k+1][j+k+1][m-k-1]) || (res[i][j+m-k][k]&&res[i+k+1][j][m-k-1])){  
              res[i][j][m]=true;  
              break;  
            }  
          }  
        }  
      }  
    }  
    return res[0][0][l-1];  
   }