首页 > 代码库 > Palindrome Partitioning II
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.
思路:先使用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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。