ขั้นตอนการแทรกขั้นต่ำเพื่อสร้างสตริง Palindrome ใน C++

สมมติว่าเรามีสตริง s เราต้องทำให้สตริงนี้เป็นพาลินโดรม ในแต่ละขั้นตอนเราสามารถแทรกอักขระใดก็ได้ในตำแหน่งใด ๆ เราต้องหาจำนวนอักขระขั้นต่ำที่ต้องใช้เพื่อสร้าง palindrome นี้ หากสตริงเป็นเหมือน "บ้า" คำตอบจะเป็น 2 เนื่องจากเราสามารถเติม "da" ก่อน "mad" หรือ "am" หลัง "mad" เพื่อสร้าง palindrome นี้ได้

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

• กำหนดฟังก์ชัน lcs() ซึ่งจะใช้เวลา s, x :=s
• n :=ขนาดของ s
• ย้อนกลับสตริง x
• s :=เชื่อมช่องว่างก่อน s, x :=ต่อช่องว่างก่อน x
• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (n + 1)
• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • สำหรับการเริ่มต้น j :=1 เมื่อ j <=n อัปเดต (เพิ่ม j โดย 1) ทำ −
    • dp[i, j] :=สูงสุดของ dp[i – 1, j] และ dp[i, j - 1]
    • ถ้า s[i] เหมือนกับ x[j] แล้ว −
      • dp[i, j] :=สูงสุดของ dp[i, j] และ dp[i – 1, j - 1] + 1
• ส่งคืน dp[n, n]
• จากวิธีการหลักขนาดส่งคืนของ s – lcs(s)

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lcs(string s){
      string x = s;
      int n = s.size();
      reverse(x.begin(), x.end());
      s = " " + s;
      x = " " + x;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      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] == x[j]){
               dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
         }
      }
      return dp[n][n];
   }
   int minInsertions(string s) {
      return s.size() - lcs(s);
   }
};
main(){
   Solution ob;
   cout << (ob.minInsertions("mad"));
}

อินพุต

“mad”

ผลลัพธ์

2