首页 > 代码库 > Palindrome Partitioning II

Palindrome Partitioning II

2024-07-17 08:00:01   223人阅读

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.

思路：先使用DP确定s中任意两个字符之间是否构成回文。若isPalindrome[step][i]为true，则表示str.substr(i,step+i)构成回文。

        然后使用一个两层的循环查找出最小划分数。

 1 class Solution { 2 public: 3     int minCut( string s ) { 4         int size = s.length(); 5         if( size <= 1 ) { return 0; } 6         vector<bool> *isPalindrome = new vector<bool>[size]; 7         isPalindrome[0].resize( size, true ); 8         for( int step = 1; step < size; ++step ) { 9             isPalindrome[step].resize( size-step, false );10             if( step == 1 ) {11                 for( int i = 0; i < size-1; ++i ) {12                     if( s[i] == s[i+1] ) { isPalindrome[1][i] = true; }13                 }14             } else {15                 for( int i = 0; i < size-step; ++i ) {16                     if( s[i] == s[i+step] && isPalindrome[step-2][i+1] ) { isPalindrome[step][i] = true; }17                 }18             }19         }20         vector<int> Q( size, 0 );21         for( int i = 1; i < size; ++i ) {22             if( isPalindrome[i][0] ) { continue; }23             Q[i] = Q[i-1]+1;24             for( int j = i-1; j > 0; --j ) {25                 if( isPalindrome[i-j][j] && Q[i] > Q[j-1]+1 ) {26                     Q[i] = Q[j-1]+1;27                     if( Q[i] == 1 ) { break; }28                 }29             }30         }31         delete [] isPalindrome;32         return Q.back();33     }34 };

 


联系
我们