C++ में एक स्ट्रिंग को दूसरी में बदलने के लिए न्यूनतम विलोपन और सम्मिलन

विवरण

आकार m और n की दो स्ट्रिंग्स str1 और str2 दी गई हैं। str1 से न्यूनतम वर्णों को हटाने और सम्मिलित करने का कार्य है ताकि इसे str2 में बदला जा सके।

Str1 = "tutorialspoint"
Str2 = "tutorials"
str1 को str2 में बदलने के लिए हमें str1 से पांच वर्ण यानी "point" हटाने होंगे।

एल्गोरिदम

1. str1 और str2 का सबसे लंबा कॉमन सबसीक्वेंस ढूंढें। इसे "lcsSize" कहें।
2. हटाए जाने वाले वर्णों की संख्या = (str1 की लंबाई - lcsSize)
3. सम्मिलित किए जाने वाले वर्णों की संख्या = (str2 की लंबाई - lcsSize)

C++ उदाहरण

#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(), 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