C ++中的回文分割
假设我们有一个输入字符串，那么当该分区的每个子字符串都是回文时，该字符串的分区就是回文分区。在本节中，我们必须找到回文分割给定字符串所需的最小切割数。因此，如果字符串像“ababbbabbababa”，则最小分割为回文。这里需要3个切口。回文是：babbbab|b|阿巴巴
为了解决这个问题，我们将遵循以下步骤-
n：=长度
分别定义nxn阶的cut矩阵和pal矩阵
对于i：=0至n
pal[i，i]：=true和cut[i，i]：=0
对于2到n范围内的len，
j：=i+len–1
如果len=2，则
如果str[i]=str[j]，则pal[i，j]：=true
否则当str[i]=str[j]和pal[i+1，j-1]≠0pal[i，j]时：=true
如果pal[i，j]为true，则cut[i，j]：=0
其他
cut[i，j]：=cut[i，j]和（cut[i，k]+cut[k+1，j+1]+1）的最小值
cut[i，j]：=∞
对于范围i至j-1的k
对于介于0到n–len之间的i，执行
返回割[0，n-1]
示例
让我们看下面的实现以更好地理解-
#include <iostream>
#include <climits>
using namespace std;
int min (int a, int b){
return (a < b)? a : b;
}
int minPalPartion(string str){
int n = str.size();
int cut[n][n];
bool pal[n][n]; //true when palindrome present for i to j th element
for (int i=0; i<n; i++){
pal[i][i] = true; //substring of length 1 is plaindrome
cut[i][i] = 0;
}
for (int len=2; len<=n; len++){
for (int i=0; i<n-len+1; i++){//find all substrings of length len
int j = i+len-1; // Set ending index
if (len == 2) //for two character string
pal[i][j] = (str[i] == str[j]);
else //for string of more than two characters
pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
if (pal[i][j] == true)
cut[i][j] = 0;
else{
cut[i][j] = INT_MAX; //initially set as infinity
for (int k=i; k<=j-1; k++)
cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);
}
}
}
return cut[0][n-1];
}
int main(){
string str= "ababbbabbababa";
cout << "Min cuts for Palindrome Partitioning is: "<<minPalPartion(str);
}输入项
ababbbabbababa
输出结果
Min cuts for Palindrome Partitioning is: 3