C++-এ একটি এনকোডেড মেসেজ ডিকোড করার প্রোগ্রাম

ধরা যাক আমাদের একটি এনকোডেড মেসেজ দেওয়া আছে যা পূর্ণসংখ্যার একটি স্ট্রিং। এই পূর্ণসংখ্যাগুলোকে বর্ণমালার নির্দিষ্ট অক্ষরের সাথে ম্যাপ করা যেতে পারে। 'a' কে ১-এ, 'b' কে ২-এ, 'c' কে ৩-এ ম্যাপ করা হয়, এবং এভাবে চলতে থাকে। এছাড়া মেসেজে '*' ক্যারেক্টারও থাকতে পারে যা ১ থেকে ৯ পর্যন্ত যেকোনো সংখ্যার সাথে ম্যাপ হতে পারে। দেওয়া 'input' স্ট্রিংটি কতভাবে ডিকোড করা যায়, তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট যদি "১৮" হয়, তবে আউটপুট হবে ২।

এই মেসেজটি দুটিভাবে ডিকোড করা সম্ভব: "ah" (১→a, ৮→h) এবং "r" (১৮→r)। সুতরাং মোট ২টি পথ আছে।

সমাধানের ধাপসমূহ

n := ইনপুট স্ট্রিংয়ের দৈর্ঘ্য
আকার n+1 এর একটি ডাইনামিক অ্যারে dynArr সংজ্ঞায়িত করুন এবং শূন্য দিয়ে আরম্ভ করুন
p := ১
k := '0'
dynArr[0] := ১
i := ১ থেকে n পর্যন্ত লুপ চালান:
- c := input[i - 1]
- যদি c '0' হয় এবং k না '1', না '2', না '*' হয়, তবে:
  - p := ০
  - লুপ থেকে বের হয়ে যান
- যদি input[i - 1] '*' হয়, তবে:
  - dynArr[i] := (dynArr[i - 1] * 9) mod m
  - যদি k '1' বা '*' হয়, তবে:
    - dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
  - যদি k '2' বা '*' হয়, তবে:
    - dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
- অন্যথায়:
  - যদি c '0' নয়, তবে dynArr[i] := dynArr[i - 1]
  - যদি k '1' বা '*' হয়, তবে:
    - dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
  - যদি (k '2' বা '*') এবং input[i - 1] <= '6' হয়, তবে:
    - dynArr[i] := (dynArr[i] + (dynArr[i - 2]) mod m) mod m
- k := c
যদি p শূন্য নয়, তবে dynArr[n] রিটার্ন করুন, অন্যথায় ০ রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝতে:

#include<bits/stdc++.h> using namespace std; const long m = 1e9 + 7; int solve(string input) {    int n = input.length();    long long dynArr[n + 1] = {0};    bool p = 1;    char k = '0';    dynArr[0] = 1;    for (int i = 1; i <= n; i++) {       char c = input[i - 1];       if (c == '0' && !(k == '1' || k == '2' || k == '*')) {          p = 0;          break;       }       if (input[i - 1] == '*') {          dynArr[i] = (dynArr[i - 1] * 9) % m;          if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2] * 9) % m;          if (k == '2' || k == '*') dynArr[i] = (dynArr[i] + (dynArr[i - 2] * 6) % m) % m;       } else {          if (c != '0') dynArr[i] = dynArr[i - 1];          if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2]) % m;          if ((k == '2' || k == '*') && input[i - 1] <= '6') dynArr[i] = (dynArr[i] + (dynArr[i - 2]) % m) % m;       }       k = c;    }    return p ? dynArr[n] : 0; } int main() { cout<< solve("18") <<endl; return 0; }