Scramble String

• bottom up dp
• Time : O(n^4)
• Space : O(n^3)

c++

int Solution::isScramble(const string A, const string B) {
    int n = A.size();
    bool dp[n+1][n+1][n+1];
    memset(dp,0,sizeof dp);
    for(int i = n - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            dp[i][j][1] = A[i] == B[j];
            for(int len = 2; i + len <= n and j + len <= n; len++) {
                for(int k = 1; k < len; k++) {
                    dp[i][j][len] |= dp[i][j][k] && dp[i+k][j+k][len-k];
                    dp[i][j][len] |= dp[i][j+len-k][k] && dp[i+k][j][len-k];
                }
            }
        }
    }
    return dp[0][0][n];
}

• top down up
• Time : O(n!)
• Space : O(n!)

c++

unordered_map<string, int> dp;

int dnc(string A, string B) {
    string k = A + "#" + B;
    if(A.length() != B.length()) return false;
    if(A == B) return true;
    if(A.length() == 1) return false;
    if(dp.count(k)) return dp[k];
    dp[k] = 0;
    for(int cut = 1; cut < A.length() and !dp[k]; cut++) {
        string caf = A.substr(0,cut), cab = A.substr(cut);
        string cbf = B.substr(0,cut), cbb = B.substr(cut);
        string rcbf = B.substr(0, B.length() - cut), rcbb = B.substr(B.length() - cut);
        dp[k] |= dnc(caf, cbf) and dnc(cab, cbb);
        dp[k] |= dnc(caf,rcbb) and dnc(cab,rcbf);
    }
    return dp[k];
}

int isScramble(const string A, const string B) {
    return dnc(A,B);
}