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