Phân vùng Palindrome II trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lần cắt cần thiết để chia chuỗi này thành các chuỗi con khác nhau và mỗi phần là một palindrome. Vì vậy, nếu chuỗi giống như "ababba", thì điều này sẽ mất 2 lần cắt. [aba | bb | a]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số ký tự trong chuỗi s

• tạo một mảng được gọi là res có kích thước n + 1

• res [n]:=-1

• đối với tôi trong phạm vi n - 1 xuống 0

  • res [i]:=n - i - 1

  • cho j trong phạm vi từ i đến n

    • nếu chuỗi con của a, từ chỉ mục i, đến j - i là một palindrome, thì

      • res [i]:=min of res [i] và 1 + res [j + 1]

• trả lại res [0]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

“ababba”

Đầu ra

2