এই সমস্যায়, আমাদের দুটি স্ট্রিং str1 এবং str2 দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে একটি স্ট্রিংকে অন্য স্ট্রিংয়ে রূপান্তর করার সম্ভাব্য সব উপায় প্রিন্ট করা যায়।
সমস্যা বর্ণনা: এখানে, আমাদের সমস্ত সম্ভাব্য উপায় খুঁজে বের করতে হবে যা ব্যবহার করে আমরা str1 কে str2 তে রূপান্তর করতে পারি। রূপান্তর করার সময়, আমরা তিনটি অপারেশনের যে কোনো একটি সম্পাদন করতে পারি,
- ঢোকান
- সরান
- প্রতিস্থাপন করুন
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: str1 =“kfeod” str2 =“kfcadq”
আউটপুট
Way1:
Insert q, after d. Replace c by e. Replace o by a.
সমাধান পদ্ধতি
আমরা প্রথমে ন্যূনতম সংখ্যা সম্পাদনা করব এবং তারপর একটি DP ম্যাট্রিক্স তৈরি করব। তারপর উভয় স্ট্রিং এর উপাদান সম্পর্কিত অক্ষর সমান কিনা তা পরীক্ষা করুন, তারপর পরিবর্তন করবেন না অন্যথায় এটি শেষ উপাদান থেকে অনুলিপি করা হয়েছে বলে আপডেট করবেন না।
এখানে, বর্তমান অক্ষর DP[i][j] =DP[i-1][j-1]। str1-এর (i-1)তম উপাদান এবং str2-এর (j-1)তম উপাদান সমান কিনা, তারপর DPকে তির্যকভাবে অতিক্রম করুন।
এখন, যদি str1-এর (i-1)তম উপাদান এবং str2-এর (j-1)তম উপাদান সমান না হয়। DP[i][j] এর মান হল (DP[i-1][j-1] , DP[i][j-1] এবং DP[i-1][j] এর মধ্যে সর্বনিম্ন মান) + 1।
এই পদ্ধতিটি একটি স্ট্রিংকে অন্য স্ট্রিং রূপান্তর করার জন্য একটি উপায় প্রিন্ট করতে পারে। সমস্ত উপায়ে প্রিন্ট করার পদ্ধতিটি কিছুটা জটিল যা একটি স্ট্রিংগুলির ভেক্টর এর মত উন্নত ডেটা কাঠামো ব্যবহার করে এবং আমরা এটি সম্পর্কে পরে শিখব।
আমাদের পদ্ধতির কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int DP[100][100];
void findWays(string str1, string str2) {
int len1 = str1.length();
int len2 = str2.length();
int i, j;
DP[len1 + 1][len2 + 1];
for (i = 0; i <= len1; i++)
DP[i][0] = i;
for (j = 0; j <= len2; j++)
DP[0][j] = j;
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1])
DP[i][j] = DP[i - 1][j - 1];
else
DP[i][j] = (min(min(DP[i - 1][j - 1], DP[i - 1][j]), DP[i][j - 1])) + 1;
}
}
while (len1 and len2) {
if (str1[len1 - 1] == str2[len2 - 1]) {
len1--;
len2--;
}
else if (DP[len1][len2] == DP[len1-1][len2-1] + 1) {
cout<<"\nModify '"<<str1[len1-1]<<"' to '"<<str2[len2-1];
len1--;
len2--;
}
else if (DP[len1][len2] == DP[len1-1][len2] + 1) {
cout<<"\nRemove "<<str1[len1-1]<<"'";
len1--;
}
else if (DP[len1][len2] == DP[len1][len2-1] + 1) {
cout <<"\nInsert '"<<str2[len2-1]<<"'";
len2--;
}
}
}
int main() {
string str1 = "kfeodge";
string str2 = "kfcadqpe";
cout<<"Way to convert one string into another string is ";
findWays(str1, str2);
return 0;
} আউটপুট
Way to convert one string into another string is Modify 'g' to 'p Insert 'q' Modify 'o' to 'a Modify 'e' to 'c
