দূরত্ব সম্পাদনা করুন

দুটি স্ট্রিং দেওয়া আছে৷ প্রথম স্ট্রিং হল সোর্স স্ট্রিং এবং দ্বিতীয় স্ট্রিং হল টার্গেট স্ট্রিং। এই প্রোগ্রামে, আমাদের খুঁজে বের করতে হবে প্রথম স্ট্রিংকে দ্বিতীয় স্ট্রিং-এ রূপান্তর করতে কতগুলি সম্ভাব্য সম্পাদনা প্রয়োজন।

স্ট্রিংগুলির সম্পাদনা হতে পারে কিছু উপাদান সন্নিবেশ করানো, প্রথম স্ট্রিং থেকে কিছু মুছে ফেলা বা দ্বিতীয় স্ট্রিং-এ রূপান্তর করতে কিছু পরিবর্তন করা৷

ইনপুট এবং আউটপুট

Input:
Two strings to compare.
string 1: Programming
string 2: Programs
Output:
Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

অ্যালগরিদম

editCount(initStr, finalStr, initLen, finalLen)

ইনপুট - প্রাথমিক এবং চূড়ান্ত স্ট্রিং এবং তাদের দৈর্ঘ্য।
আউটপুট - initStr থেকে finalStr করার জন্য সম্পাদনার সংখ্যা প্রয়োজন।

Begin
   if initLen = 0, then
      return finalLen
   if finalLen := 0, then
      return initLen

   if initStr[initLen - 1] = finalStr[finalLen - 1], then
      return editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   answer := 1 + min of (editCount(initStr, finalStr, initLen , finalLen - 1)),
      (editCount(initStr, finalStr, initLen – 1, finalLen ),
      (editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   return answer
End

উদাহরণ

#include<iostream>
using namespace std;

int min(int x, int y, int z) {       //find smallest among three numbers
   if(x < y) {
      if(x < z)
         return x;
      else
         return z;
   }else {
      if(y < z)
         return y;
      else
         return z;
   }
}

int editCount(string initStr , string finalStr, int initLen, intfinalLen) {
   if (initLen == 0)       //when initial string is empty, add all characters of final string
      return finalLen;

   if (finalLen == 0)       //when final string is empty, delete all characters from initial string
      return initLen;

   //when last character matches, recursively check previous characters
   if (initStr[initLen-1] == finalStr[finalLen-1])
      return editCount(initStr, finalStr, initLen-1, finalLen-1);

   //if last character match is not found, check for insert, delete and update operations recursively
   return 1 + min ( editCount(initStr, finalStr, initLen, finalLen- 1),  // insert
 
      editCount(initStr, finalStr, initLen-1, finalLen), // delete
      editCount(initStr, finalStr, initLen-1, finalLen-1) // update
   );
}

int main() {
   string initStr;
   string finalStr;

   cout << "Enter the initial string: "; cin >> initStr;
   cout << "Enter the final string: "; cin >> finalStr;
   cout << "The number of changes required to convert " << initStr << " to " << finalStr;
   cout << " is " << editCount( initStr , finalStr, initStr.size(), finalStr.size()) << endl;
}

আউটপুট

Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4