हमें एक स्ट्रिंग दी गई है जो अंक श्रृंखला को दर्शाती है। प्रत्येक अंक को 1 से 26 तक अंग्रेजी वर्णमाला के रूप में डिकोड किया जाता है। 1 'A' है, 2 'B' है और इसी तरह 26 'Z' है। लक्ष्य दी गई अंक श्रृंखला से सभी संभावित डिकोडिंग की संख्या ज्ञात करना है। यदि श्रृंखला '123' है तो संभावित डिकोडिंग हैं 'ABC' (1-2-3), 'LC' (12-3), 'AW' (1-23)। गिनती 3 है।
उदाहरण सहित समझ
इनपुट - str[]="1532"
आउटपुट - दी गई अंक श्रृंखला के संभावित डिकोडिंग की संख्या: 2
व्याख्या - संभावित डिकोडिंग हैं AECB - (1-5-3-2) और OCB (15-3-2)।
इनपुट - str[]="216"
आउटपुट - दी गई अंक श्रृंखला के संभावित डिकोडिंग की संख्या: 3
व्याख्या - संभावित डिकोडिंग हैं "BAF" (2-1-6), "UF" (21-6), "BP" (2-16)।
प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम इसे एक रिकर्सिव विधि का उपयोग करके करेंगे। इस रिकर्सिव विधि को स्ट्रिंग के भाग पास करें।
जांचें कि अंतिम अंक '0' नहीं है, यदि सही है, तो 0 और लंबाई-1 के बीच की शेष स्ट्रिंग जांचें। जांचें कि अंतिम दो अंकों का स्ट्रिंग भाग 1 और 26 के बीच की संख्या बनाता है या नहीं। यदि सही है, तो काउंट अपडेट करें और 0 और लंबाई-2 के बीच की शेष स्ट्रिंग जांचें।
- इनपुट को स्ट्रिंग
str[]के रूप में लें। - फंक्शन
decode_digit_seq(char *str, int length)स्ट्रिंग और इसकी लंबाई लेता है और str के संभावित डिकोडिंग की गिनती लौटाता है। - यदि लंबाई 0 है। 1 लौटाएँ।
- यदि लंबाई 1 है। 1 लौटाएँ।
- यदि अंतिम एकल वर्ण गैर-शून्य है, तो काउंट
decode_digit_seq(str, length-1)होगा। - यदि अंतिम से दूसरा वर्ण '1' है तो अंतिम दो अंक 10 और 19 (J से S) के बीच होंगे, काउंट को अपडेट करें:
count = count + decode_digit_seq(str, length-2)। - यदि अंतिम से दूसरा वर्ण '2' है और अंतिम वर्ण '<7' है तो अंतिम दो अंक 20 और 26 (T से Z) के बीच होंगे, काउंट को अपडेट करें:
count = count + decode_digit_seq(str, length-2)। - अब सभी मामले कवर हो गए हैं।
- अंत में सभी रिकर्सन के बाद परिणाम के रूप में काउंट लौटाएँ।
उदाहरण
#include <iostream>
#include <cstring>
using namespace std;
int decode_digit_seq(char *str, int length) {
int count = 0;
if (length == 0) {
return 1;
}
if (length == 1) {
return 1;
}
if (str[0] == '0') {
return 0;
}
if (str[length-1] > '0') {
count = decode_digit_seq(str, length-1);
}
if (str[length-2] == '1') {
count = count + decode_digit_seq(str, length-2);
}
if (str[length-2] == '2' && str[length-1] < '7') {
count = count + decode_digit_seq(str, length-2);
}
return count;
}
int main() {
char str[] = "7651";
int length = strlen(str);
cout << "Count of Possible Decodings of a given Digit Sequence are: " << decode_digit_seq(str, length);
return 0;
}
आउटपुट
Count of Possible Decoding of a given Digit Sequence are: 1
