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

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

इसलिए, यदि इनपुट इनपुट ="18" जैसा है, तो आउटपुट 2 होगा।

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=इनपुट की लंबाई
एक सरणी dynArr आकार की परिभाषित करें:n+1 और इसे शून्य से प्रारंभ करें
p :=1
k :='0'
dynArr[0] :=1
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
- c :=इनपुट[i - 1]
- यदि c, 0 के समान है और नहीं (k, '1' के समान है या k, '2' के समान है या k, '*' के समान है), तो −
  - p :=0
  - लूप से बाहर आएं
- यदि इनपुट [i - 1] '*' के समान है, तो −
  - dynArr[i] :=(dynArr[i - 1] * 9) mod m
  - यदि k, '1' के समान है या k, '*' के समान है, तो −
    - dynArr[i] :=(dynArr[i] + dynArr[i - 2] * 9) mod m
  - यदि k, '2' के समान है या k, '*' के समान है, तो −
    - dynArr[i] :=(dynArr[i] + (dynArr[i - 2] * 6) मॉड एम) मॉड एम
- अन्यथा,
  - यदि c '0' के बराबर नहीं है, तो -
  - - यदि k, '1' के समान है या k, '*' के समान है, तो −
      - dynArr[i] :=(dynArr[i] + dynArr[i - 2]) मॉड m
    - यदि (k '2' के समान है या k '*' के समान है) और इनपुट [i - 1] <='6', तो −
      - dynArr[i] :=(dynArr[i] + (dynArr[i - 2]) mod m) मॉड 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) % m;
      }
      k = c;
   }
   return p ? dynArr[n] : 0;
}

int main() {
   cout<< solve("18") <<endl;
   return 0;
}