C++-এ একটি স্ট্রিং থেকে অন্য স্ট্রিং-এ কনভার্ট করার সব সম্ভাব্য পথ প্রিন্ট করুন

দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। str1-কে str2-এ কনভার্ট করার সব সম্ভাব্য পথ বের করতে হবে। অনুমোদিত অপারেশন:

• Insert — ক্যারেক্টার যোগ করা
• Remove — ক্যারেক্টার মুছে ফেলা
• Replace — ক্যারেক্টার প্রতিস্থাপন

উদাহরণ

ইনপুট: str1 = "kfeod", str2 = "kfcadq"

আউটপুট (একটি সম্ভাব্য পথ):

Way1:
Insert q, after d. Replace c by e. Replace o by a.

অ্যালগরিদম (ডাইনামিক প্রোগ্রামিং - এডিট ডিস্ট্যান্স)

1. DP[i][j] = str1[0..i-1]-কে str2[0..j-1]-এ কনভার্ট করার মিনিমাম এডিট সংখ্যা।
2. বেস কেস: DP[i][0] = i (সব ডিলিট), DP[0][j] = j (সব ইনসার্ট)।
3. ট্রানজিশন:
   • str1[i-1] == str2[j-1] → DP[i][j] = DP[i-1][j-1]
   • অন্যথায় → DP[i][j] = 1 + min(DP[i-1][j-1], DP[i][j-1], DP[i-1][j]) (রিপ্লেস, ইনসার্ট, ডিলিট)
4. ব্যাকট্র্যাকিং করে পথ রিকনস্ট্রাক্ট করুন।

C++ প্রোগ্রাম (একটি পথ প্রিন্ট করে)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int DP[100][100];

void findWays(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    for (int i = 0; i <= len1; i++) DP[i][0] = i;
    for (int j = 0; j <= len2; j++) DP[0][j] = j;
    for (int i = 1; i <= len1; i++) {
        for (int 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({DP[i-1][j-1], DP[i-1][j], DP[i][j-1]}) + 1;
        }
    }
    while (len1 && 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'

নোট

• এই কোড একটি অপ্টিমাল পথ প্রিন্ট করে।
• সব সম্ভাব্য পথ প্রিন্ট করতে vector এবং রিকার্সিভ ব্যাকট্র্যাকিং লাগে (আধিক্য জটিল)।
• টাইম কমপ্লেক্সিটি: O(len1 × len2)।