数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究回文划分 II（C++）
假设我们有一个字符串 s，我们必须找出将这个字符串分割成多个子字符串并使每部分都成为回文的所需的切割次数。因此，如果字符串类似于“ababba”，那么这将需要两次切割。[aba|bb|a]
要解决这个问题，我们将遵循以下步骤 −
n := 字符串 s 中的字符数
创建一个称为 res 的数组，大小为 n + 1
res[n] := -1
对于 n – 1 到 0 范围内的 i
res[i] := n – i – 1
对于 i 到 n 范围内的 j
如果从索引 i 到 j – i 的子字符串 a 是回文，则
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
更新时间：2020-05-26
122 次浏览
广告