程序在C ++中字符串的最小分割数之后计算回文数
假设我们有一个小写的字符串s，我们必须将它分成尽可能少的字符串，以使每个字符串都是回文，然后找到字符串的数量。
因此，如果输入类似于s=“levelracecar”，则输出将为2，因为有两个回文式“level”和“racecar”。
在线示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
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] + 1;
}
};
int solve(string s) {
return (new Solution())->solve(s);
}
int main(){
string s = "levelracecar";
cout << solve(s);
}输入值
"levelracecar"输出结果
2