দুটি স্ট্রিং দেওয়া আছে। প্রথম স্ট্রিংটি হলো সোর্স স্ট্রিং এবং দ্বিতীয়টি হলো টার্গেট স্ট্রিং। এই প্রোগ্রামে, আমাদের খুঁজে বের করতে হবে প্রথম স্ট্রিংকে দ্বিতীয় স্ট্রিংে রূপান্তর করতে কতগুলো এডিট (সম্পাদনা) প্রয়োজন।
স্ট্রিংয়ের এডিট হতে পারে: কিছু এলিমেন্ট ইনসার্ট করা, প্রথম স্ট্রিং থেকে কিছু ডিলিট করা, অথবা কিছু মডিফাই করা যাতে দ্বিতীয় স্ট্রিংয়ে রূপান্তর হয়।
ইনপুট এবং আউটপুট
ইনপুট: তুলনা করার জন্য দুটি স্ট্রিং। string 1: Programming string 2: Programs আউটপুট: 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 বানাতে কতগুলো এডিট প্রয়োজন।
শুরু
যদি initLen = 0, তবে
return finalLen
যদি finalLen = 0, তবে
return initLen
যদি initStr[initLen - 1] = finalStr[finalLen - 1], তবে
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
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
using namespace std;
int min(int x, int y, int z) {
// তিনটি সংখ্যার মধ্যে সবচেয়ে ছোটটি খুঁজে বের করুন
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, int finalLen) {
if (initLen == 0) // যখন প্রাথমিক স্ট্রিং খালি, ফাইনাল স্ট্রিংর সব ক্যারেক্টার যোগ করুন
return finalLen;
if (finalLen == 0) // যখন ফাইনাল স্ট্রিং খালি, প্রাথমিক স্ট্রিংর সব ক্যারেক্টার ডিলিট করুন
return initLen;
// যখন শেষ ক্যারেক্টার মিলে যায়, রিকারসিভভাবে আগের ক্যারেক্টার চেক করুন
if (initStr[initLen-1] == finalStr[finalLen-1])
return editCount(initStr, finalStr, initLen-1, finalLen-1);
// যদি শেষ ক্যারেক্টার মিলে না যায়, ইনসার্ট, ডিলিট এবং আপডেট অপারেশন রিকারসিভভাবে চেক করুন
return 1 + min(
editCount(initStr, finalStr, initLen, finalLen-1), // ইনসার্ট
editCount(initStr, finalStr, initLen-1, finalLen), // ডিলিট
editCount(initStr, finalStr, initLen-1, finalLen-1) // আপডেট
);
}
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
