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.

C++:
01 class Solution {
02 public:
03     int minCut(string s) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=s.size();
07         vector<int> A(n);
08         vector<bool* > P(n);
09         for(int i=0;i<n;i++)
10         {
11             P[i]=new bool[n];
12             P[i][i]=true;
13         }
14         for(int i=1;i<n;i++)
15         {
16             for(int j=0;j<ni;j++)
17             {
18                 if(s[j]!=s[j+i])
19                 {
20                     P[j][j+i]=false;
21                     continue;
22                 }
23                 if(i<2)
24                 {
25                     P[j][j+i]=true;
26                     continue;
27                 }
28                 P[j][j+i]=P[j+1][j+i1];
29             }
30         }
31         for(int i=n1;i>=0;i)
32         {
33             if(P[i][n1])
34             {
35                 A[i]=0;
36                 continue;
37             }
38             int tmp=n;
39             for(int j=i;j<n;j++)
40             {
41                 if(P[i][j])
42                 {
43                     int m=A[j+1]+1;
44                     if(m<tmp)
45                         tmp=m;
46                 }
47             }
48             A[i]=tmp;
49         }
50         return A[0];
51     }
52 };
Advertisements
This entry was posted in Dynamic programming, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s