โปรแกรมนับจำนวนพาลินโดรมหลังแบ่งสตริงน้อยที่สุดใน C++

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

ตัวอย่าง: s = "levelracecar" ผลลัพธ์คือ 2 เพราะแบ่งได้เป็น "level" และ "racecar" ซึ่งทั้งคู่เป็นพาลินโดรม

ขั้นตอนการแก้ปัญหา

1. n := ความยาวของสตริง A
2. สร้างอาร์เรย์ result ขนาด n+1
3. result[n] := -1
4. วนลูป i จาก n-1 ถึง 0:
   • result[i] := n - i - 1 (ค่าสูงสุดที่เป็นไปได้)
   • วนลูป j จาก i ถึง n-1:
     • ถ้าส่วนย่อย A[i..j] เป็นพาลินโดรม:
       • result[i] = min(result[i], 1 + result[j+1])
5. คืนค่า result[0] + 1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isPalindrome(string A) {
        int left = 0, right = A.size() - 1;
        while (left < right) {
            if (A[left] != A[right]) return false;
            left++; right--;
        }
        return true;
    }
    
    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);
    return 0;
}

อินพุต

"levelracecar"

เอาต์พุต

2