a********r
发帖数: 217 | 1 在leetcode上总是TLE, 基本想法是：建一个二维表（vector>）vvi记录
所有palindrome的位置，如果s[i]是一个palindrome的开头，则vvi[i]的vector记录所
有的下一个palindrome的开始位置。Vector dp记录最小分割数，dp[i]是sub
string s[i...n-]的最小分割数。从右到左扫描vvi,就可以建立dp[].最后输出dp[0].
这个方法应该是O(n^2) time 和 O(n^2) space.
int minCut(string s) {
int n=s.size();
if(s.size()==1) return 0;
if(setTable(s)) return 0;
vector dp(n);// dp[i] store the minCut for s[i...n-1]
dp[n-1]=0;
for(int i=n-2; i>=0;i--){
dp[i]=n-i-1;
for(auto it=vvi[i].begin();it!=vvi[i].end();it++){
if(*it==n) dp[i]=0;
if(dp[*it]+1
}
}
return dp[0];
}
int setTable(string s){ // set up a table vvi such that vvi[i] record all
the next Palindrome start position.
int n=s.size();
vvi.resize(n);
for(int i=n-1;i>=0;i--){ // first search how many positions could arrive
at the end of s;
if(isPalindrome(s.substr(i))) vvi[i].push_back(n);
}
if(!vvi[0].empty() && vvi[0][0]==n) return 0; //if we there is a
palindrome starting 0, then the cut is 0;
for(int i=s.size()-1;i>=0;i--){
if(!vvi[i].empty()){ //if vvi[i] is not empty then start searching
all palindromes ended at s[i-1].
for(int j=i-1;j>=0;j--){
if(isPalindrome(s.substr(j,i-j))){
vvi[j].push_back(i);//found one mark vvi[j] with i.
}
}
}
return 1;
}
bool isPalindrome(string s){
if(s.size()==1) return true;
for(int i=0,j=s.size()-1;i
if(s[i]!=s[j]) return false;
}
return true;
} |
|
