सी ++ में दो स्ट्रिंग्स के लिए ऑपरेशन हटाएं

मान लीजिए कि हमारे पास दो शब्द w1 और w2 हैं, हमें w1 और w2 को समान बनाने के लिए आवश्यक चरणों की न्यूनतम संख्या ज्ञात करनी है, जहां प्रत्येक चरण में हम किसी भी स्ट्रिंग में एक वर्ण को हटा सकते हैं। . इसलिए यदि इनपुट "समुद्र" और "खाने" की तरह है, तो आउटपुट 2 होगा, क्योंकि हमें w1 से 's' को हटाना होगा, यह "ea" होगा और w2 से "ईट" से "t" को हटा देगा। फिर वे वही हैं।

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

n :=s1 का आकार, m :=s2 का आकार
स्ट्रिंग्स s1 और s2 से पहले एक रिक्त स्थान जोड़ें, फिर s1 और s2 को तदनुसार अपडेट करें
आकार की एक तालिका बनाएं (n + 1) x (m + 1)
i के लिए :=1 से m
- dp[0, i] :=dp[0, i - 1] + 1
i के लिए:=1 से n
- dp[i, 0] :=dp[i – 1, 0] + 1
मैं के लिए 1 से n की सीमा में
- जे के लिए 1 से मी की सीमा में
  - अगर s1[i] =s2[j]
    - dp[i, j] :=dp[i – 1, j-1]
  - else dp[i, j] =न्यूनतम dp[i-1, j] + 1 और dp[i, j-1] + 1
रिटर्न डीपी[एन, एम]

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minDistance(string s1, string s2) {
      int n = s1.size();
      int m = s2.size();
      s1 = " " + s1;
      s2 = " " + s2;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= m; i++){
         dp[0][i] = dp[0][i - 1] + 1;
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + 1;
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s1[i] == s2[j]){
               dp[i][j] = dp[i - 1][j - 1];
            }
            else{
               dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.minDistance("sea", "eat"));
}

इनपुट

"sea"
"eat"