C++-এ ওয়ান এডিট ডিস্ট্যান্স

দুটি স্ট্রিং s ও t দেওয়া আছে। আমাদের চেক করতে হবে সেগুলো এক এডিট ডিস্ট্যান্সে আছে কিনা। এক এডিট ডিস্ট্যান্স তিন ধরনের হতে পারে:

s-এ একটি ক্যারেক্টার ইনসার্ট করে t পাওয়া
s-থেকে একটি ক্যারেক্টার ডিলিট করে t পাওয়া
s-এর একটি ক্যারেক্টার রিপ্লেস করে t পাওয়া

যেমন, s = "ab", t = "acb" হলে আউটপুট হবে true

সমাধানের ধাপগুলো:

n := s.size(), m := t.size()
যদি n < m হয়, তবে isOneEditDistance(t, s) কল করব
প্রতি i এর জন্য 0 থেকে m-1 পর্যন্ত:
- যদি s[i] != t[i] হয়, তবে:
  - যদি n == m হয় (রিপ্লেস), তবে s.substr(i+1) == t.substr(i+1) চেক করব
  - অন্যথায় (ইনসার্ট), s.substr(i+1) == t.substr(i) চেক করব
লুপ শেষে 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;
    }
};

int main() {
    Solution ob;
    cout << (ob.isOneEditDistance("ab", "acb"));
}

ইনপুট

s = "ab", t = "acb"