ขั้นตอนน้อยที่สุดทำให้สตริงเป็นพาลินโดรมใน C++

คำอธิบายปัญหา

ให้สตริง s ในแต่ละขั้นตอนสามารถแทรกตัวอักษรได้ที่ตำแหน่งใดก็ได้ หาจำนวนขั้นตอนน้อยที่สุดทำให้ s กลายเป็น palindrome

ตัวอย่าง

s = "mad" → Output: 2
แทรก "da" หน้า → "damad" หรือแทรก "am" หลัง → "madam"

แนวทางแก้ปัญหา: LCS กับสตริงกลับ

จำนวนการแทรกน้อยที่สุด = |s| - LCS(s, reverse(s))

เพราะ LCS ระหว่าง s และ reverse(s) คือ longest palindromic subsequence ตัวอักษรที่ไม่อยู่ใน LPS ต้องแทรกคู่ให้ครบ

DP สำหรับ LCS

dp[i][j] = LCS ของ s[1..i] และ rev[1..j]
if s[i] == rev[j]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

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

class Solution {
    int lcs(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        int n = s.size();
        s = " " + s; rev = " " + rev; // 1-indexed
        
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(s[i] == rev[j])
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            }
        return dp[n][n];
    }
    
public:
    int minInsertions(string s) {
        return s.size() - lcs(s);
    }
};

ความซับซ้อน

• เวลา: O(n²)
• พื้นที่: O(n²) (ลดเป็น O(n) ได้)