सी++ में स्ट्रिंग पैलिंड्रोम बनाने के लिए न्यूनतम निवेशन चरण

मान लीजिए कि हमारे पास एक स्ट्रिंग है, हमें यह स्ट्रिंग पैलिंड्रोम बनाना है। प्रत्येक चरण में हम किसी भी स्थिति में किसी भी वर्ण को सम्मिलित कर सकते हैं, हमें इस पैलिंड्रोम को बनाने के लिए आवश्यक वर्णों की न्यूनतम संख्या ज्ञात करनी होगी। यदि स्ट्रिंग "पागल" की तरह है, तो उत्तर 2 होगा क्योंकि हम इस पैलिंड्रोम को बनाने के लिए "पागल" से पहले "दा" या "पागल" के बाद "एम" जोड़ सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें lcs(), इसमें s, x:=s लगेगा
• n :=आकार का
• स्ट्रिंग x को उल्टा करें
• s :=s से पहले स्पेस को जोड़ना, x :=x से पहले स्पेस को जोड़ना
• एक 2D सरणी dp आकार (n + 1) x (n + 1) परिभाषित करें
• इनिशियलाइज़ i :=1 के लिए, जब i <=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
• रिटर्न डीपी[एन, एन]
• मुख्य विधि से 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