87. Scramble String

Problem from leetcode 87. Scramble String

---

这是一道典型的 dynamic programming 问题。

---

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int size = s1.size();
        if(size != s2.size()) return false;
        if(size == 0 && s2.size() == 0) return true;
        
        //dp[i][j][k] = true means s1(i,...,i+k-1) 
        //is a scramble of s2(j,...,j+k-1)
        int dp[size][size][size+1];
        memset(dp, false, sizeof(dp));
        
        for(int k = 1; k <= size; ++k)
            for(int i = 0; i <= size-k; ++i)
                for(int j = 0; j <= size-k; ++j)
                {
                    if(k == 1)
                        dp[i][j][k] = (s1[i]==s2[j]);
                    else
                    {
                        //now seperate s1(i,...,i+k-1) to 
                        //two parts: left parts and right parts
                        for(int left = 1; left < k; ++left)
                        {
                            if(dp[i][j][left] && dp[i+left][j+left][k-left])
                                dp[i][j][k] = true;
                            if(dp[i][j+k-left][left] && dp[i+left][j][k-left])
                                dp[i][j][k] = true;
                        }
                    }
                }
        return dp[0][0][size];
            
    }
};

Above code is O(n⁴) time complexity.
Java:

public class Solution {
    public boolean isScramble(String s1, String s2) {
        int size = s1.length();
        if(size != s2.length()) return false;
        if(size == 0 && s2.length() == 0) return true;
        
        //dp[i][j][k] = true means s1(i,...,i+k-1) is a 
        //scramble of s2(j,...,j+k-1)
        boolean[][][] dp = new boolean[size][size][size+1];

        for(int k = 1; k <= size; ++k)
            for(int i = 0; i <= size-k; ++i)
                for(int j = 0; j <= size-k; ++j)
                {
                    if(k == 1)
                        dp[i][j][k] = (s1.charAt(i)==s2.charAt(j));
                    else
                    {
                        //now seperate s1(i,...,i+k-1) to 
                        //two parts: left parts and right parts
                        for(int left = 1; left < k; ++left)
                        {
                            if(dp[i][j][left] && dp[i+left][j+left][k-left])
                                dp[i][j][k] = true;
                            if(dp[i][j+k-left][left] && dp[i+left][j][k-left])
                                dp[i][j][k] = true;
                        }
                    }
                }
        return dp[0][0][size];
    }
}