Simple DP solution with C++, however slow


  • 0
    I
    bool isScramble(string& s1, string& s2) {
        int a = s1.size() + 1, b = s2.size() + 1;
        if (a != b) return false;
        vector<vector<vector<bool> > > dp(a, vector<vector<bool> >(a, vector<bool> (a, false)));
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < a; j++) {
                dp[1][i][j] = s1[i - 1] == s2[j - 1];
            }
        }
        for (int k = 2; k < a; k++) {
            for (int t = 1; t < k; t++) {
                for (int i = 1; i < a - k + 1; i++) {
                    for (int j = 1; j < a - k + 1; j++) {
                        if ((dp[t][i][j] && dp[k - t][i + t][j + t]) ||
                            (dp[t][i][j + k - t] && dp[k - t][i + t][j])) {
                            dp[k][i][j] = true; 
                        }
                    }
                }
            }
        }
        return dp[a - 1][1][1]; 
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.