Các bước chèn tối thiểu để tạo chuỗi Palindrome trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tạo chuỗi này là palindrome. Trong mỗi bước, chúng ta có thể chèn bất kỳ ký tự nào ở bất kỳ vị trí nào, chúng ta phải tìm số ký tự tối thiểu cần thiết để tạo palindrome này. Nếu chuỗi giống như "mad", thì câu trả lời sẽ là 2 vì chúng ta có thể thêm "da" trước "mad" hoặc "am" sau "mad" để tạo ra palindrome này.

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

• Xác định một hàm lcs (), hàm này sẽ lấy s, x:=s
• n:=kích thước của s
• đảo ngược chuỗi x
• s:=nối khoảng trắng trước s, x:=nối khoảng trắng trước x
• Xác định một dp mảng 2D có kích thước (n + 1) x (n + 1)
• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
  • để khởi tạo j:=1, khi j <=n, cập nhật (tăng j lên 1), thực hiện -
    • dp [i, j]:=tối đa của dp [i - 1, j] và dp [i, j - 1]
    • nếu s [i] giống với x [j] thì -
      • dp [i, j]:=tối đa của dp [i, j] và dp [i - 1, j - 1] + 1
• trả về dp [n, n]
• Từ phương thức chính, kích thước trả về là s - lcs (s)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

“mad”

Đầu ra

2