palindrome partitioningII

palindrome partitioningII

DP

dp[i] stand s.substr(0,i-1)'s minum cut. dp[i] is the minnum of three values.

  • i-1
  • dp[i-1]+1
  • dp[j-1]+1substring from j-1 to i-1 is palindrome
 1 class Solution {
 2 public:
 3     int minCut(string s) {
 4         int l = s.length();
 5         int dp[l+1];
 6         dp[0] = -1;
 7         for ( int i = 1; i <= l; i++ ) {
 8             dp[i] = i-1;
 9         }
10         for ( int i = 1; i <= l ; i++ ) {
11             int j = min(i,l-i+1)-1;
12             int k = 1;
13             dp[i] = min(dp[i],dp[i-1]+1);
14             while ( k <= j ) {
15                 if ( s[i-1-k] == s[i+k-1] ) {
16                     dp[i+k] = min(dp[i+k],dp[i-k-1]+1);
17                 } else {
18                     break;
19                 }
20                 k++;
21             }
22             j = min(i,l-i)-1;
23             k = 0;
24             while ( k <= j ) {
25                 if ( s[i-1-k] == s[i+k] ) {
26                     dp[i+k+1] = min(dp[i+k+1],dp[i-k-1]+1);
27                 } else {
28                     break;
29                 }
30                 k++;
31             }
32         }
33         return dp[l];
34     }
35 };

This solution seems a little hard to undersitand. i stands for the middle of the palindrome string. j stands for the max length of the left and right of this string. k means the iterative varable.

Loading Disqus comments...
Table of Contents