सी ++ में एक स्ट्रिंग को दूसरे में बदलने के लिए संचालन प्राप्त करने का कार्यक्रम

मान लीजिए कि हमारे पास दो तार S और T हैं। हमें संचालन का सबसे छोटा अनुक्रम खोजना है जो S को T में बदलता है। यहां संचालन मूल रूप से या तो हटा रहा है या एक वर्ण सम्मिलित कर रहा है।

इसलिए, यदि इनपुट S ="xxxy" T ="xxyy" जैसा है, तो आउटपुट ["x", "x", "-x", "y", "+y"] होगा, इसका अर्थ है स्थान पहले दो x, फिर तीसरा x निकालें, फिर y रखें और फिर एक नया y जोड़ें।

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

• 505 x 505 आकार की एक टेबल डीपी बनाएं
• एक फ़ंक्शन सहायता परिभाषित करें (), इसमें i, j, S, T,
लगेगा
• यदि i, S के आकार के समान है और j, T के आकार के समान है, तो −
  • रिटर्न डीपी[i, j] =0
• यदि i, S के आकार के समान है, तो −
  • रिटर्न डीपी[i, j] =1 + सहायता (i, j + 1, S, T)
• यदि j, T के आकार के समान है, तो −
  • रिटर्न डीपी[i, j] =1 + सहायता (i + 1, j, S, T)
• यदि dp[i, j] -1 के बराबर नहीं है, तो −
  • रिटर्न डीपी[i, j]
• न करें:=1e5, डेल:=0, सम्मिलित करें:=0
• यदि S[i], T[j] के समान है, तो −
  • न करें:=सहायता (i + 1, j + 1, S, T)
• del :=1 + सहायता (i + 1, j, S, T)
• सम्मिलित करें:=1 + सहायता(i, j + 1, S, T)
• minVal:=min({dontDo, del, insert})
• रिटर्न डीपी[i, j] =minVal
• एक फ़ंक्शन को परिभाषित करें getPath(), इसमें i, j, S, T, curr, एक सरणी रेट,
लगेगा
• यदि curr 0 के समान है और i, S के आकार के समान है और j, T के आकार के समान है, तो −
  • वापसी
• यदि मैं <एस का आकार और जे <टी और एस का आकार [i] टी [जे] और डीपी [i + 1, j + 1] के समान है, तो −
  • रिटर्न के अंत में स्ट्रिंग(1, एस[i]) डालें
  • getPath(i + 1, j + 1, S, T, curr, ret)
• अन्यथा जब dp[i + 1, j] + 1 curr के समान हो, तो −
  रिट के अंत में
  • सम्मिलित करें ("-" स्ट्रिंग को संयोजित करें(1, S[i]))
  • getPath(i + 1, j, S, T, curr-1, ret)
• अन्यथा
  रिट के अंत में
  • सम्मिलित करें ("+" स्ट्रिंग को संयोजित करें(1, T[j]))
  • getPath(i, j + 1, S, T, curr-1, ret)
• मुख्य विधि से निम्न कार्य करें -
• डीपी को -1 से भरें
• एक सरणी रिट परिभाषित करें
• x :=सहायता (0, 0, एस, टी)
• getPath(0, 0, S, T, x, ret)
• रिटर्न रिटर्न

उदाहरण (C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}
int dp[505][505];
class Solution {
   public:
   int help(int i, int j, string& S, string& T) {
      if (i == S.size() && j == T.size())
         return dp[i][j] = 0;
      if (i == S.size())
         return dp[i][j] = 1 + help(i, j + 1, S, T);
      if (j == T.size())
         return dp[i][j] = 1 + help(i + 1, j, S, T);
      if (dp[i][j] != -1)
         return dp[i][j];
      int dontDo = 1e5;
      int del = 0;
      int insert = 0;
      if (S[i] == T[j])
         dontDo = help(i + 1, j + 1, S, T);
      del = 1 + help(i + 1, j, S, T);
      insert = 1 + help(i, j + 1, S, T);
      int minVal = min({dontDo, del, insert});
      return dp[i][j] = minVal;
   }
   void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
      if (curr == 0 && i == S.size() && j == T.size())
         return;
      if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
         ret.push_back(string(1, S[i]));
         getPath(i + 1, j + 1, S, T, curr, ret);
      }else if (dp[i + 1][j] + 1 == curr) {
         ret.push_back("-" + string(1, S[i]));
         getPath(i + 1, j, S, T, curr - 1, ret);
      }else {
         ret.push_back("+" + string(1, T[j]));
         getPath(i, j + 1, S, T, curr - 1, ret);
      }
   }  
   vector<string> solve(string S, string T) {
      memset(dp, -1, sizeof dp);
      vector<string> ret;
      int x = help(0, 0, S, T);
      getPath(0, 0, S, T, x, ret);
      return ret;
   }
};
vector<string> solve(string source, string target) {
   return (new Solution())->solve(source, target);
}
main(){
   string S = "xxxy", T = "xxyy";
   print_vector(solve(S, T));
}

इनपुट

"xxxy", "xxyy"

आउटपुट

[x, x, -x, y, +y, ]