C++ 中的回文分割
c++server side programmingprogramming
假设我们有一个输入字符串，该字符串的分割即为回文分割，即分割的每个子串都是回文。在本节中，我们需要找到对给定字符串进行回文分割所需的最小切割。如果字符串类似于"ababbbabbababa"，则需要进行回文分割所需的最小切割。这里需要 3 个切割。回文为:a | babbbab | b | ababa
为了解决这个问题，我们将遵循以下步骤 −
- n := str 的长度
- 定义 cut 矩阵和 pal 矩阵，每个矩阵的阶数均为 n x n
- 对于 i := 0 到 n，执行
- pal[i, i] := true 且 cut[i, i] := 0
- 对于 len 在 2 到 n 范围内的情况，执行
- 对于 i 在 0 到 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] 为 0 时，pal[i, j] := true
- 如果 pal[i, j] 为 true，则 cut[i, j] := 0
- 否则
- cut[i, j] := ∞
- 对于 i 到 j-1 范围内的 k，执行
- cut[i, j] := cut[i, j] 和 (cut[i, k]+ cut[k+1, j+1]+1) 中的最小值
- 对于 i 在 0 到 n 范围内的情况 – len，执行
- return cut[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]; //当第 i 到 j 个元素存在回文时为 true
for (int i=0; i<n; i++){
pal[i][i] = true; //长度为 1 的子字符串为回文
cut[i][i] = 0;
}
for (int len=2; len<=n; len++){
for (int i=0; i<n-len+1; i++){//查找所有长度为 len 的子字符串
int j = i+len-1; // 设置结束索引
if (len == 2) //对于两个字符的字符串
pal[i][j] = (str[i] == str[j]);
else //对于两个以上字符的字符串
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; //初始设置为无穷大
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 << "回文分割的最小切割是: "<<minPalPartion(str);
}
输入
ababbbabbababa
输出
回文分割的最小切割是: 3
