Palindrome Partitioning II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/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.

代码：

 class Solution {  
 public:  
   int minCut(string s) {  
     int N = s.size();  
     // isP[0]: [0,i] is palindrome  
     bool isP[N]; // [j,i] is palindrome; j = [0, 1, ..., i-1]  
     int dp[N];  
     dp[0] = 0;  
     for (int i = 1; i < N; ++i) { // end point  
       isP[i] = true;  
       dp[i] = dp[i-1] + 1; // dp[i-1] + single word cut  
       for (int j = 0; j < i; ++j) {  
         isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true  -> [j...i] is a palindrome; ascending order  
                           // isP[j+1] == true -> [j+1...i-1] is a palindrome  
         if (isP[j]) {  
           dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]            
         }  
       }  
     }  
     return dp[N-1];  
   }  
 };  
   
 // Time Limit Exceed  
 class Solution {  
 public:  
   //Version 2: sequence dp; easier to understand isP  
   void getIsPalindrome(const string &s, vector<vector<bool> > &isP) {  
     int N = s.size();  
     // isP[i][j] (start i, end j is palindrome)  
     for (int i = 0; i < N; ++i) {  
       isP[i][i] = true;        
     }  
     for (int l = 2; l <= N; ++l) {  
       for (int i = 0; i <= N - l; ++i) {  
         isP[i][i + l - 1] = false;  
         if (l == 2) {  
           isP[i][i + l - 1] = (s[i] == s[i + 1]);  
         } else {  
           isP[i][i + l - 1] = (s[i] == s[i + l - 1] && isP[i + 1][i + l - 2]);  
         }    
       }  
     }  
   }  
   
   int minCut(string s) {  
     int N = s.size();  
     vector<vector<bool>> isP(N, vector<bool>(N, false));  
     getIsPalindrome(s, isP);  
     vector<int> dp(N, 0);  
     dp[0] = 0;  
     for (int i = 1; i < N; ++i) {  
       dp[i] = dp[i - 1] + 1;  
       for (int j = 0; j < i; ++j) {  
         if (j == 0 && isP[j][i]) {  
           dp[i] = 0;   
           break;  
         } else if (isP[j][i]) {  
           dp[i] = min(dp[i], dp[j - 1] + 1);  
         }  
       }  
     }  
     return dp[N - 1];  
   }  
 };