题目
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.
思路
此题可以用动态规划求解。isPal[j][i]表示字符串s的子串s[j…i]是否为回文串,cut[i]表示子串s[0…i]所需要的最小分割数
代码
/**------------------------------------
* 日期:2015-03-02
* 作者:SJF0115
* 题目: 132.Palindrome Partitioning II
* 网址:https://oj.leetcode.com/problems/palindrome-partitioning-ii/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
public:
int minCut(string s) {
int size = s.size();
if(size == 0){
return 0;
}//if
// isPal[i][j]表示字符串s的子串s[i,j]是否为回文串
bool isPal[size][size];
memset(isPal,0,sizeof(isPal));
// cut[j]表示子串s[0,j]所需要的最小分割数
int cut[size];
// cut[0,i]
for(int i = 0;i < size;++i){
// [0,i]最多分割i次
cut[i] = i;
// 判断s[j,i]是否是回文串
for(int j = 0;j <= i;++j){
// s[j,i]是回文串
if(s[j] == s[i] && (i - j <= 1 || isPal[j+1][i-1])){
isPal[j][i] = true;
// s[0,i]是回文串
if(j == 0){
cut[i] = 0;
}//if
else{
cut[i] = min(cut[i],cut[j-1]+1);
}//else
}//if
}//for
}//for
return cut[size-1];
}
};
int main(){
Solution s;
string str("cabababcbc");
cout<<s.minCut(str)<<endl;
return 0;
}
运行时间
时间: 2024-12-13 19:55:52