मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं; हमें जांचना है कि क्या वे दोनों वन एडिट डिस्टेंस पर हैं। वन एडिट डिस्टेंस के तीन प्रकार हैं:
s में एक कैरेक्टर डालकर t प्राप्त करना
s से एक कैरेक्टर हटाकर t प्राप्त करना
s के एक कैरेक्टर को बदलकर t प्राप्त करना
इसलिए, यदि इनपुट है s = "ab", t = "acb", तो आउटपुट True होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
n := s का आकार, m := t का आकार
यदि n < m, तो -
isOneEditDistance(t, s) लौटाएं
i := 0 से शुरू करें, जब i < m, i बढ़ाते हुए, करें -
यदि s[i], t[i] के बराबर नहीं है, तो -
यदि n, m के समान है, तो -
true लौटाएं जब s का सबस्ट्रिंग इंडेक्स 0 से (i) तक, t के सबस्ट्रिंग इंडेक्स 0 से (i) तक के समान हो
true लौटाएं जब s का सबस्ट्रिंग इंडेक्स 0 से (i) तक, t के सबस्ट्रिंग इंडेक्स 0 से (i - 1) तक के समान हो
true लौटाएं जब 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
