Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. To scramble the string, we may choose any non-leaf node and swap its two children. Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

难度：hard

Solution: Recursive

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length()) {
            return false;
        }
        if(s1.equals(s2)) {
            return true;
        }
        if(s1.length() == 1) {
            return false;
        }
        int length = s1.length();

        int[] letters = new int[26];
        for(int i = 0; i < length; i++){
            letters[s1.charAt(i)-'a']++;
            letters[s2.charAt(i)-'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(letters[i]!= 0) {
                return false;
            }
        }
        for(int i = 1; i < length; i++){
            if((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) 
               || (isScramble(s1.substring(0, i), s2.substring(length - i)) && isScramble(s1.substring(i), s2.substring(0, length - i)))) {
                return true;
            }
        }
        return false;

    }
}

Solution: Dynamic Programming

/**
* Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
* Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
* Let q be the length of a cut (hence, q < k), then we are in the following situation:
*
* S1 [ x1 | x2 ]
* i i + q i + k - 1
*
* here we have two possibilities:
*
* S2 [ y1 | y2 ]
* j j + q j + k - 1
*
* or
*
* S2 [ y1 | y2 ]
* j j + k - q j + k - 1
*
* which in terms of F means:
*
* F(i, j, k) = for some 1 <= q < k we have:
* (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
*
* Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal
* */
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length()) {
            return false;
        }
        int length = s1.length();
        boolean[][][] dp = new boolean[length][length][length + 1];
        for(int i = 0; i < length; ++i) {
            for(int j = 0; j < length; ++j) {
                dp[i][j][0] = true;
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for(int k = 2; k <= length; ++k) {
            for(int i = 0; i + k - 1 < length; ++i) {
                for(int j = 0; j + k - 1 < length; ++j) {
                    for(int l = 1; l < k; ++l) {
                        dp[i][j][k] |= ((dp[i][j][l] && dp[i + l][j + l][k - l]) || (dp[i][j + k - l][l] && dp[i + l][j][k - l]));
                    }
                }
            }
        }
        return dp[0][0][length];   
    }
}