14 lines. My accepted O(n^2) DP solution in C++


  • 0
    S
    class Solution {
    public:
        int minCut(string s) {
            vector<vector<bool>> is_pal(s.length(), vector<bool>(s.length(), false));
            for (int i = s.length() - 1; i >= 0; i--)
            for (int l = 0;l <= s.length() - i; l++)
                is_pal[i][l] = l<2?true:(is_pal[i + 1][l - 2] & s[i] == s[i + l - 1]);
            vector<int> dp(s.length(), INT_MAX >> 1);
            for (int i = 0;i < s.length(); i++)
            for (int j = 0;j <= i; j++)
                dp[i] = min(dp[i], is_pal[j][i - j + 1]?(j>0?dp[j-1]+1:0):(INT_MAX>>1));
            return dp[s.length() - 1];
        }
    };

Log in to reply
 

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