इस समस्या में हमें दो तार str1 और str2 दिए जाते हैं। हमारा काम एक स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के सभी संभावित तरीकों को प्रिंट करने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण: यहां, हमें उन सभी संभावित तरीकों को खोजने की जरूरत है जिनके उपयोग से हम str1 को str2 में बदल सकते हैं। कनवर्ट करते समय, हम तीनों में से कोई भी ऑपरेशन कर सकते हैं,
- सम्मिलित करें
- निकालें
- बदलें
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: str1 ="kfeod" str2 ="kfcadq"
आउटपुट
Way1:
Insert q, after d. Replace c by e. Replace o by a.
समाधान दृष्टिकोण
हम पहले न्यूनतम संख्या में संपादन पाएंगे और फिर एक डीपी मैट्रिक्स बनाएंगे। फिर जांचें कि क्या दोनों स्ट्रिंग्स में तत्व से संबंधित वर्ण समान है, फिर संशोधित न करें अन्यथा अपडेट करें क्योंकि यह अंतिम तत्व से कॉपी किया गया है।
यहाँ, वर्तमान वर्ण 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] andDP[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