โปรแกรมนับจำนวน palindromes หลังจากจำนวนการแยกสตริงขั้นต่ำใน C++

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องแยกมันออกเป็นสตริงให้น้อยที่สุดเท่าที่จะทำได้ เพื่อให้แต่ละสตริงเป็นพาลินโดรม แล้วจึงหาจำนวนสตริง

ดังนั้น หากอินพุตเป็น s ="levelracecar" เอาต์พุตจะเป็น 2 เนื่องจากมี "ระดับ" และ "racecar" ของ palindromes สองแห่ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• กำหนดผลลัพธ์ของขนาดอาร์เรย์ (n + 1)

• ผลลัพธ์[n] :=-1

• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ผลลัพธ์[i] :=n - i - 1

  • สำหรับการเริ่มต้น j :=i เมื่อ j

    • ถ้าสตริงย่อยของ A จากช่วง i ถึง j - i เป็นพาลินโดรม ดังนั้น −

      • ผลลัพธ์[i] :=ผลลัพธ์ขั้นต่ำ[i] และ 1 + ผลลัพธ์[j + 1]

• ส่งคืนผลลัพธ์[0] + 1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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