array based C++ Solution


  • 0
    F
    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if (s1.size() != s2.size()) return false;
            if (s1 == s2) return true;
            int n = s1.size();
            //vector<vector<vector<bool>>> dp(n, vector<vector<bool>(n, vector<bool>(n + 1, false)));
            bool dp[n][n][n+1];
            memset(dp, 0, n*n*(n+1));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j][1] = (s1[i]==s2[j]);
                }
            }
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    for (int j = 0; j <= n - len; j++) {
                        for (int k = 1; k < len; k++) {
                            if ((dp[i][j][k] && dp[i+k][j+k][len-k]) || 
                                (dp[i+k][j][len-k] && dp[i][j+len-k][k])) {
                                dp[i][j][len] = true;        
                            }
                        }
    
                    }
                }
            }
            return dp[0][0][n];
        }
    };

Log in to reply
 

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