विवरण
क्रमशः m और n आकार के दो तार str1 और str2 दिए गए हैं। कार्य str1 से/में कम से कम वर्णों को हटाना और सम्मिलित करना है ताकि इसे str2 में परिवर्तित किया जा सके।
Str1 = “tutorialspoint” Str2 = “tutorials” To transform str1 to str2 we have to delete five characters i.e. “point” from str1.
एल्गोरिदम
1. Find longest common subsequence of str1 and str2. Let’s call it as “lcsSize” 2. Number of characters to be deleted = (length of str1 - lcsSize) 3. Number of characters to be inserted = (length of 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