C ++中的回文分割II
为了解决这个问题，我们将遵循以下步骤-
n:=字符串s中的字符数
创建一个名为res的数组，大小为n+1
res[n]：=-1
对于范围n–1到0的i
res[i]：=n–i–1
对于i到n范围内的j
如果a的子串，从索引i到j–i是一个回文，那么
res[i]：=res[i]和1+res[j+1]的最小值
返回res[0]
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string A) {
int left = 0;
int right = A.size()-1;
while(left < right) {
if(A[left] != A[right]) {
return 0;
}
left++;
right--;
}
return 1;
}
int solve(string A) {
int n = A.size();
vector<int>result(n+1);
result[n] = -1;
for(int i=n-1;i>=0;i--) {
result[i] = n-i-1;
for(int j=i;j<n;j++) {
if(isPalindrome(A.substr(i, j-i+1))) {
result[i] = min(result[i], 1 + result[j+1]);
}
}
}
return result[0];
}
class Solution {
public:
int minCut(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.minCut("ababba"));
}输入值
“ababba”
输出结果
2