C++ में दिए गए संदेश को डिकोड करने का प्रोग्राम

मान लीजिए हमें एक एन्कोडेड संदेश दिया गया है जो पूर्णांक संख्याओं की एक स्ट्रिंग है। अब, इन पूर्णांक संख्याओं को वर्णमाला के एक विशिष्ट अक्षर से मैप किया जा सकता है। 'a' को 1 से, 'b' को 2 से, 'c' को 3 से मैप किया जाता है, और इसी तरह आगे। एक वर्ण '*' भी होता है जो संदेश में हो सकता है और जिसे 1 से 9 तक की किसी भी संख्या से मैप किया जा सकता है। तो दिए गए संदेश 'input' के लिए, हमें यह पता लगाना है कि इसे कितने तरीकों से डिकोड किया जा सकता है।

उदाहरण के लिए, यदि इनपुट "18" है, तो आउटपुट 2 होगा।

संदेश को "ah" के रूप में डिकोड किया जा सकता है, क्योंकि 1 'a' से मैप होता है और 8 'h' से। साथ ही, संख्या "r" से भी मैप हो सकती है, क्योंकि 18 'r' से मैप होता है। इसलिए, इनपुट को डिकोड करने के कुल 2 तरीके हैं।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

n := input की लंबाई
आकार n+1 का एक सरणी dynArr परिभाषित करें और इसे शून्य से आरंभ करें
p := 1
k := '0'
dynArr[0] := 1
i := 1 से n तक लूप चलाएं:
- c := input[i - 1]
- यदि c '0' के समान है और k न तो '1', न '2', न '*' है, तो:
  - p := 0
  - लूप से बाहर निकलें
- यदि 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
- k := c
यदि p शून्येतर है, तो dynArr[n] लौटाएं, अन्यथा 0 लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#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;       }       k = c;    }    return p ? dynArr[n] : 0; } int main() { cout<< solve("18") <<endl; return 0; }