सी++ में वन एडिट डिस्टेंस

मान लीजिए कि हमारे पास दो तार s और t हैं; हमें यह जांचना होगा कि क्या वे दोनों एक संपादन दूरी अलग हैं। एक संपादन दूरी तीन प्रकार की होती है -

• t प्राप्त करने के लिए s में एक वर्ण डालें

• t प्राप्त करने के लिए s से एक वर्ण हटाएं

• t पाने के लिए s का वर्ण बदलें

इसलिए, यदि इनपुट s ="ab", t ="acb" जैसा है, तो आउटपुट सही होगा

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

• n :=s का आकार, m :=t का आकार

• अगर एन <एम, तो -

  • वापसी isOneEditDistance(t, s)

• इनिशियलाइज़ करने के लिए मैं :=0, जब i

  • अगर s[i] t[i] के बराबर नहीं है, तो -

    • यदि n, m के समान है, तो -

      • जब इंडेक्स 0 से (i) में s का सबस्ट्रिंग इंडेक्स 0 से (i) में t के सबस्ट्रिंग के समान हो, तो सही लौटें

    • जब इंडेक्स 0 से (i) में s का सबस्ट्रिंग इंडेक्स 0 से (i - 1) में t के सबस्ट्रिंग के समान हो, तो सही लौटें

• जब m + 1 n के समान हो तो सही लौटें

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isOneEditDistance(string s, string t) {
      int n = s.size();
      int m = t.size();
      if (n < m) {
         return isOneEditDistance(t, s);
      }
      for (int i = 0; i < m; i++) {
         if (s[i] != t[i]) {
            if (n == m) {
               return s.substr(i + 1) == t.substr(i + 1);
            }
            return s.substr(i + 1) == t.substr(i);
         }
      }
      return m + 1 == n;
   }
};
main(){
   Solution ob;
   cout << (ob.isOneEditDistance("ab", "acb"));
}

इनपुट

s = "ab", t = "acb"

आउटपुट

1