C++ এ এক সম্পাদনা দূরত্ব

ধরুন আমাদের দুটি স্ট্রিং আছে s এবং t; আমাদের পরীক্ষা করতে হবে যে তারা উভয়ই এক সম্পাদনা দূরত্ব আলাদা কিনা। এক সম্পাদনা দূরত্ব তিন প্রকার −

• টি

  পেতে s-এ একটি অক্ষর সন্নিবেশ করুন

• t পেতে s থেকে একটি অক্ষর মুছুন

• t

  পেতে s-এর একটি অক্ষর প্রতিস্থাপন করুন

সুতরাং, ইনপুট যদি s ="ab", t ="acb" এর মত হয়, তাহলে আউটপুট হবে True

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s এর আকার, m :=t এর আকার

• যদি n

  • রিটার্ন isOneEditDistance(t,s)

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি s[i] t[i] এর সমান না হয়, তাহলে −

    • যদি n m এর সমান হয়, তাহলে −

      • সূচী 0 থেকে (i) থেকে s-এর সাবস্ট্রিং 0 থেকে (i) থেকে t-এর সাবস্ট্রিং-এর সমান হলে সত্য ফেরত দিন

    • সূচী 0 থেকে (i) থেকে s-এর সাবস্ট্রিং 0 থেকে (i - 1) সূচী থেকে t-এর সাবস্ট্রিং-এর সমান হলে সত্য ফেরত দিন

• যখন m + 1 n

  এর মত একই হয় তখন true রিটার্ন করুন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#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