Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
是这个题吧。
bool check(const string& s, int j, int i){
while( j <= i && a[j++] == a[i--] );
if( j > i ) return true;
return false;
}
int PalinPartition(const string& s){
if( s.empty() ) return -1;
vector T(s.size(),numeric_limits::max());
for( int i = 0; i < s.size(); ++i ){
if( check(s,0,i) ){
T[i] = 0;
break;
}
for( int j = 1; j <= i; ++j )
if( check(s, j, i) && T[i] > T[j-1] + 1 )
T[i] = T[j-1]+1;
}
return T[s.size()-1];
}
这个复杂度是O(n^3)（我之前以为是n^2，后来发现check也是O(n), LZ应该也是这个DP
吧），这个只输出最小parti的个数，稍微修改一下用backtrack的方法
，T 存parti的位置，就可以求出所有substring。
