C++ ব্যবহার করে একটি স্ট্রিংকে অন্য স্ট্রিংয়ে রূপান্তরের ন্যূনতম ডিলিশন ও ইনসারশন

বিবরণ

আকার m এবং n এর দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। str1 থেকে ন্যূনতম কতগুলো ক্যারেক্টার ডিলিট এবং ইনসার্ট করলে সেটি str2-এ রূপান্তরিত হবে তা বের করতে হবে।

Str1 = "tutorialspoint"
Str2 = "tutorials"
str1 কে str2-এ রূপান্তর করতে str1 থেকে পাঁচটি ক্যারেক্টার "point" ডিলিট করতে হবে।

এলগরিদম

1. str1 এবং str2-এর লংগেস্ট কমন সাবসিকোয়েন্স (LCS) বের করুন। এটাকে 'lcsSize' বলুন।
2. ডিলিট করার ক্যারেক্টার সংখ্যা = (str1 দৈর্ঘ্য - lcsSize)
3. ইনসার্ট করার ক্যারেক্টার সংখ্যা = (str2 দৈর্ঘ্য - lcsSize)

উদাহরণ কোড

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

int lcs(string s1, string s2, int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    }
    if (s1[m - 1] == s2[n - 1]) {
        return 1 + lcs(s1, s2, m - 1, n - 1);
    } else {
        return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
    }
}

void minDeletionAndInsertion(string s1, string s2) {
    int m = s1.size();
    int n = s2.size();
    int lcsSize = lcs(s1, s2, m, n);
    cout << "Min deletion = " << (m - lcsSize) << endl;
    cout << "Min insertion = " << (n - lcsSize) << endl;
}

int main() {
    minDeletionAndInsertion("tutorialspoint", "tutorials");
    return 0;
}

আউটপুট

প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:

Min deletion = 5 Min insertion = 0