Description

Submission

class Solution {
    int dp[2005][2005];
public:
    bool checkPartitioning(string s) {
        int n = s.size();

        for(int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        for(int i = 1; i < n; ++i) {
            if(s[i] == s[i-1]) dp[i-1][i] = 1;
        }

        // the loop should be based on stiring length
        for(int len = 3; len <= n; ++len) {
            for(int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                if(s[i] == s[j]) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        for(int i = 0; i < n - 1; ++i) {
            for(int j = i+2; j < n; ++j) {
                if(dp[0][i] && dp[i+1][j-1] && dp[j][n-1]) return true;
            }
        }

        return false;
    }
};