C ++中的回文分割II

假设我们有一个字符串s，我们必须找到将这个字符串分成不同的子字符串所需的剪切数，并且每个部分都是回文。因此，如果字符串像“ ababba”，则将需要2次切割。[aba | bb | a]

为了解决这个问题，我们将遵循以下步骤-

• 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