Chương trình đếm số palindromes sau số lần chia nhỏ nhất của chuỗi trong C ++

Giả sử chúng ta có một chuỗi chữ thường s, chúng ta phải chia nó thành càng ít chuỗi càng tốt sao cho mỗi chuỗi là một palindrome và sau đó tìm số chuỗi.

Vì vậy, nếu đầu vào là s =​​"levelracecar", thì đầu ra sẽ là 2, vì có hai palindromes "level" và "racecar".

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

• n:=kích thước của A

• Xác định kết quả mảng có kích thước (n + 1)

• kết quả [n]:=-1

• để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • kết quả [i]:=n - i - 1

  • để khởi tạo j:=i, khi j

    • nếu chuỗi con của A từ phạm vi i đến j - i là palindrome, thì -

      • result [i]:=tối thiểu của kết quả [i] và 1 + kết quả [j + 1]

• trả về kết quả [0] + 1

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

Đầu vào

"levelracecar"

Đầu ra

2