s*****1
发帖数: 134 | 1 这leetcode 新题 Palindrome Partitioning 我的算法时间是O(N^2)
Palindrome Partitioning2 如果用1的方法做，似乎也就是O(N^2),
但用DP做，似乎要O(N^3),反正我没通过大测试
请问，第二题有没有比第一题简单快速的方法额~DP复杂度也在O(N^2)内
谢谢 | r*********n
发帖数: 4553 | 2 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。 | s*****1
发帖数: 134 | 3 恩，谢谢回复~
我觉得楼主的DP方法很妙
另外这个check的方法也可以DP的，
用一个boolean[start][end]来储存是否为palindrome，这样的预先处理一下只要O(N^2
),然后用到时还是O(1)来判断，
所以最终是能做到O(N^2)的~ | r*********n
发帖数: 4553 | 4 Thanks for the input
^2
【在 s*****1 的大作中提到】
: 恩，谢谢回复~
: 我觉得楼主的DP方法很妙
: 另外这个check的方法也可以DP的，
: 用一个boolean[start][end]来储存是否为palindrome，这样的预先处理一下只要O(N^2
: ),然后用到时还是O(1)来判断，
: 所以最终是能做到O(N^2)的~
|
|
