Palindrome Partitioning - LeetCode 131

[Question]

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.

[Analysis]

The minimum cut of the string S at position i is,
     MinimumCuts(i) = MinimumCuts[j-1]+1, while  S[j] ...S[i] is the longest palindrome sub-string ending at position i.  (j<i).

Use a table to calculate the palindrome sub-string at each position. C[i,j] is true when S[j,i]  is a palindrome. C[i,j] is true, when C[i-1, j+1] is true && S[i] == S[j].

Total time complex is O(N^2).

[Solution]

    int minCut(string s) {
        if (s.size()==0) return 0;
     
        int len = s.size();
     
        int dp[len+1];
        for (int i=0; i<len+1; i++)
            dp[i] = i;

        bool c[len+1][len+1];
        for (int i=0; i<=len; i++)
            for (int j=0; j<=len; j++)
            c[i][j] = false;
         
        c[0][0]=true;
        for (int i=1; i<len+1; i++)
            for (int j=i; j>0; j--) {
                if (s[i-1]==s[j-1] && (i-j<2 || c[i-1][j+1]==true)) {
                    c[i][j] = true;
                    dp[i] = min(dp[i], dp[j-1]+1);
                }
            }
     
        return dp[len]-1;
    }