दो स्ट्रिंग्स दी गई हैं। पहली स्ट्रिंग स्रोत स्ट्रिंग है और दूसरी स्ट्रिंग लक्ष्य स्ट्रिंग है। इस प्रोग्राम में, हमें यह ढूंढना है कि पहली स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के लिए कितने संभावित संपादन की आवश्यकता है।
स्ट्रिंग्स का संपादन या तो कुछ तत्व डालना हो सकता है, पहली स्ट्रिंग से कुछ हटाना या दूसरी स्ट्रिंग में बदलने के लिए कुछ संशोधित करना।
इनपुट और आउटपुट
इनपुट: तुलना के लिए दो स्ट्रिंग्स। स्ट्रिंग 1: Programming स्ट्रिंग 2: Programs आउटपुट: प्रारंभिक स्ट्रिंग दर्ज करें: Programming अंतिम स्ट्रिंग दर्ज करें: Programs Programming को Programs में बदलने के लिए आवश्यक परिवर्तनों की संख्या 4 है
एल्गोरिदम
editCount(initStr, finalStr, initLen, finalLen)
इनपुट: प्रारंभिक और अंतिम स्ट्रिंग और उनकी लंबाई।
आउटपुट: initStr को finalStr बनाने के लिए आवश्यक संपादनों की संख्या।
शुरू यदि initLen = 0, तो वापस करें finalLen यदि finalLen := 0, तो वापस करें initLen यदि initStr[initLen - 1] = finalStr[finalLen - 1], तो वापस करें editCount(initStr, finalStr, initLen – 1, finalLen - 1) answer := 1 + min of (editCount(initStr, finalStr, initLen , finalLen - 1)), (editCount(initStr, finalStr, initLen – 1, finalLen ), (editCount(initStr, finalStr, initLen – 1, finalLen - 1) answer वापस करें अंत
उदाहरण
#include<iostream> using namespace std; int min(int x, int y, int z) { //तीन संख्याओं में सबसे छोटी खोजें if(x < y) { if(x < z) return x; else return z; }else { if(y < z) return y; else return z; } } int editCount(string initStr , string finalStr, int initLen, int finalLen) { if (initLen == 0) //जब प्रारंभिक स्ट्रिंग खाली हो, तो अंतिम स्ट्रिंग के सभी वर्ण जोड़ें return finalLen; if (finalLen == 0) //जब अंतिम स्ट्रिंग खाली हो, तो प्रारंभिक स्ट्रिंग से सभी वर्ण हटाएं return initLen; //जब अंतिम वर्ण मेल खाता हो, तो पिछले वर्णों को पुनरावर्ती रूप से जांचें if (initStr[initLen-1] == finalStr[finalLen-1]) return editCount(initStr, finalStr, initLen-1, finalLen-1); //यदि अंतिम वर्ण मेल नहीं खाता, तो सम्मिलन, हटाने और अद्यतन संचालन के लिए पुनरावर्ती रूप से जांचें return 1 + min ( editCount(initStr, finalStr, initLen, finalLen- 1), // सम्मिलन editCount(initStr, finalStr, initLen-1, finalLen), // हटाना editCount(initStr, finalStr, initLen-1, finalLen-1) // अद्यतन ); } int main() { string initStr; string finalStr; cout << "Enter the initial string: "; cin >> initStr; cout << "Enter the final string: "; cin >> finalStr; cout << "The number of changes required to convert " << initStr << " to " << finalStr; cout << " is " << editCount( initStr , finalStr, initStr.size(), finalStr.size()) << endl; }
आउटपुट
Enter the initial string: Programming Enter the final string: Programs The number of changes required to convert Programming to Programs is 4
