Scramble String 430

Question

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.

Challenge

O(n3) time

Solution

这道题可以用递归的方法解。对于s1和s2，找不同的分割点k，将其分别分为两个子数组。若s1的两个子数组和对应的s2的两个子数组都是scramble的，则s1和s2就是scramble的。例如，s1[0...i]被分为0...k，k+1...i，其对应的s2子数组为0...k，k+1...i或者0...i-k-1, i-k...i（即s2的前k个元素或者后k个元素对应于s1的前k个元素，比如s1=abc，s2=acb，第一层递归时比较的是s1左边的子数组和s2左边的子数组以及s1右边的子数组和s2右边的子数组，第二层递归比较右边两个子数组时，就要比较s1右边子数组的左边子数组"b"和s2右边子数组的右边子数组"b"），只要两种情况里面有一种满足，则s1和s2就是scramble的。因此：

( isScramble(s2[0...k], s1[0...k]) && isScramble(s2[k+1...j], s1[k+1...i]) ) || ( isScramble(s2[0...k], s1[i-k...i]) && isScramble(s2[k+1...j], s1[0...i-k-1]) )，（k = 0,1,2 ... i-1，k相当于字符串的分割点)

只要一个子问题返回ture，那么就表示两个字符串可以转换。

因为递归解法有很多重复子问题，比如s2 = rgeat, s1 = great 当我们选择分割点为0时，要解决子问题 isScramble(reat, geat)，再对该子问题选择分割点0时，要解决子问题 isScramble(eat,eat)；而当我们第一步选择1作为分割点时，也要解决子问题 isScramble(eat,eat)。相同的子问题isScramble(eat,eat)就要解决2次。

因此可以用记忆化搜索来保存子问题，设dp[i][j][k]表示s2从j开始长度为k的子串是否可以由s1从i开始长度为k的子串转换而成，那么动态规划方程如下:

状态方程： dp[i][j][k] = ( dp[i][j][divlen] && dp[i+divlen][j+divlen][k-divlen]) || ( dp[i][j+k-divlen][divlen] && dp[i+divlen][j][k-divlen] ) (divlen = 1,2,3...k-1, 它表示子串分割点到子串起始端的距离) ，只要一个子问题返回真，就可以停止计算

代码如下：

DP:

public class Solution {
    /**
     * @param s1 A string
     * @param s2 Another string
     * @return whether s2 is a scrambled string of s1
     */
    public boolean isScramble(String s1, String s2) {
        // Write your code here
        int[][][] dp = new int[n][n][n + 1];
        return checkScramble(s1, 0, s2, 0, n, dp);

    }

    private boolean checkScramble(String s1, int s1Start, String s2, int s2Start, int len, int[][][] dp){
        if(dp[s1Start][s2Start][len] == 1){
            return true;
        }
        if(dp[s1Start][s2Start][len] == -1){
            return false;
        }

        if(s1.length() != s2.length()){
            return false;
        }

        if(s1.length() == 0 || s1.equals(s2)){
            dp[s1Start][s2Start][len] = 1;
            return true;
        }

        if(!isValid(s1, s2)){
            dp[s1Start][s2Start][len] = -1;
            return false;
        }

        for(int k = 1; k < len; k++){
            String s1Left = s1.substring(0, k);
            String s1Right = s1.substring(k, len);

            String s2Left = s2.substring(0, k);
            String s2Right = s2.substring(k, len);

            if(checkScramble(s1Left, s1Start, s2Left, s2Start, k, dp) && checkScramble(s1Right, s1Start + k, s2Right, s2Start + k, len - k, dp)){
                dp[s1Start][s2Start][len] = 1;
                return true;
            }

            s2Left = s2.substring(0, len - k);
            s2Right = s2.substring(len - k, len);

            if(checkScramble(s1Left, s1Start, s2Right, s2Start + len - k, k, dp) && checkScramble(s1Right, s1Start + k, s2Left, s2Start, len - k, dp)){
                dp[s1Start][s2Start][len] = 1;
                return true;
            }
        }

        dp[s1Start][s2Start][len] = -1;
        return false;

    }

    private boolean isValid(String s1, String s2){
        char[] array1 = s1.toCharArray();
        char[] array2 = s2.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        if(!new String(array1).equals(new String(array2))){
            return false;
        }
        return true;
    }
}

Recursion

public class Solution {
    /**
     * @param s1 A string
     * @param s2 Another string
     * @return whether s2 is a scrambled string of s1
     */
    public boolean isScramble(String s1, String s2) {
        // Write your code here
        //Recursion
        if(s1 == null && s2 == null){
            return true;
        }

        if(s1 == null || s2 == null){
            return false;
        }

        if(s1.length() != s2.length()){
            return false;
        }

        if(s1.length() == 0 || s1.equals(s2)){
            return true;
        }

        if(!isValid(s1, s2)){
            return false;
        }

        int n = s1.length();
        for(int k = 1; k < n; k++){
            String s1Left = s1.substring(0, k);
            String s1Right = s1.substring(k);
            String s2Left = s2.substring(0, k);
            String s2Right = s2.substring(k);
            if(isScramble(s1Left, s2Left) && isScramble(s1Right, s2Right)){
                return true;
            }
            s2Left = s2.substring(0, n - k);
            s2Right = s2.substring(n - k);
            if(isScramble(s1Left, s2Right) && isScramble(s1Right, s2Left)){
                return true;
            }
        }
        return false;
    }

    private boolean isValid(String s1, String s2){
        char[] array1 = s1.toCharArray();
        char[] array2 = s2.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        if(!new String(array1).equals(new String(array2))){
            return false;
        }
        return true;
    }
}