আমাদের একটি স্ট্রিং দেওয়া আছে যা একটি ডিজিট সিকোয়েন্স উপস্থাপন করে। প্রতিটি ডিজিট ১ থেকে ২৬ পর্যন্ত ইংরেজি বর্ণমালা অনুযায়ী ডিকোড হয়: ১='A', ২='B', ..., ২৬='Z'। লক্ষ্য হলো দেওয়া ডিজিট সিকোয়েন্স থেকে সম্ভাব্য সব ডিকোডিংয়ের সংখ্যা বের করা। যদি সিকোয়েন্স '১২৩' হয়, তবে সম্ভাব্য ডিকোডিং: 'ABC' (১-২-৩), 'LC' (১২-৩), 'AW' (১-২৩)। মোট ৩টি।
উদাহরণ দিয়ে বুঝি
ইনপুট − str[]="1532"
আউটপুট − দেওয়া ডিজিট সিকোয়েন্সের সম্ভাব্য ডিকোডিং সংখ্যা: ২
ব্যাখ্যা − সম্ভাব্য ডিকোডিং: AECB (১-৫-৩-২) এবং OCB (১৫-৩-২)।
ইনপুট − str[]="216"
আউটপুট − সম্ভাব্য ডিকোডিং সংখ্যা: ৩
ব্যাখ্যা − সম্ভাব্য ডিকোডিং: "BAF" (২-১-৬), "UF" (২১-৬), "BP" (২-১৬)।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা রিকার্সিভ পদ্ধতি ব্যবহার করব। স্ট্রিং-এর অংশগুলো এই রিকার্সিভ ফাংশনে পাস করব।
- ইনপুট হিসেবে স্ট্রিং
str[]নিন। decode_digit_seq(char *str, int length)ফাংশন স্ট্রিং এবং এর দৈর্ঘ্য নিয়ে সম্ভাব্য ডিকোডিং কাউন্ট রিটার্ন করে।- যদি
length == 0, ১ রিটার্ন করুন। - যদি
length == 1, ১ রিটার্ন করুন। - যদি শেষ ডিজিট '০' নয়, তবে
count = decode_digit_seq(str, length-1)। - যদি শেষ থেকে দ্বিতীয় ডিজিট '১' হয়, তবে শেষ দুই ডিজিট ১০ থেকে ১৯ (J থেকে S) এর মধ্যে পড়ে।
count = count + decode_digit_seq(str, length-2)আপডেট করুন। - যদি শেষ থেকে দ্বিতীয় ডিজিট '২' হয় এবং শেষ ডিজিট '৭' ছোট হয়, তবে শেষ দুই ডিজিট ২০ থেকে ২৬ (T থেকে Z) এর মধ্যে পড়ে।
count = count + decode_digit_seq(str, length-2)আপডেট করুন। - সব কেস কভার হয়েছে। সব রিকার্সনের পর
countরিটার্ন করুন।
উদাহরণ
#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
