132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example,
given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if ( n == 0 ) return 0;
        vector<int> res(n, 0);
        res[0] = 0;
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for ( int i = n-1; i >= 0; i-- ) {
            for ( int j = i; j <= n-1; j++ ){
                if ( ( j-i <= 1 or isPal[i+1][j-1] ) and s[i] == s[j] ) {
                    isPal[i][j] = true;
                }
            }
        }
        for ( int i = 1; i <= n-1; i++ ) {
            if ( isPal[0][i] ) {res[i] = 0; continue;}
            res[i] = i;
            for ( int j = 0; j <= i-1; j++ ) {
                if ( not isPal[j+1][i] ) continue;
                res[i] = min(res[i], res[j] + 1);
            }
        }
        return res[n-1];
    }
};