C++ में डिकोड तरीके II

मान लीजिए कि एक संदेश है, जिसमें ए-जेड के अक्षरों को निम्नलिखित मैपिंग तरीके का उपयोग करके संख्याओं में एन्कोड किया जा रहा है -

'ए' -> 1, 'बी' -> 2, ..., 'जेड' -> 26

अब, एन्कोडेड स्ट्रिंग में वर्ण '*' भी हो सकता है, जिसे 1 से 9 तक की संख्याओं में से एक के रूप में माना जा सकता है। इसलिए यदि हमारे पास अंक और वर्ण '*' युक्त एन्कोडेड संदेश है, तो हमें खोजना होगा इसे डिकोड करने के तरीकों की कुल संख्या। यदि उत्तर बहुत लंबा है, तो हम अंतिम परिणाम प्राप्त करने के लिए मॉड 109 + 7 का उपयोग कर सकते हैं। तो अगर इनपुट केवल * है, तो 9 संभावित तरीके हो सकते हैं, ये सभी 1 से 9 तक की संख्याएं हैं, इसलिए ये A से I हैं।

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

• एक फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
लगेगा
• वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
• एक फ़ंक्शन mul() परिभाषित करें, इसमें a, b,
लगेगा
• वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम
• मुख्य विधि से निम्न कार्य करें -
• n :=आकार का
• n + 1 आकार की dp सरणी परिभाषित करें
• dp[0] :=1
• यदि s[0] '0' के समान है, तो −
  • वापसी 0
• dp[1] :=9 जब s[0] '*' के समान हो अन्यथा 1
• इनिशियलाइज़ i :=2 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
  करें
  • पहला :=s[i - 2], दूसरा :=s[i - 1]
  • यदि दूसरा '*' के समान है, तो −
    • dp[i] :=add(dp[i], mul(9, dp[i - 1]))
  • अन्यथा जब दूसरा> '0', तब −
    • dp[i] :=dp[i - 1]
  • यदि पहला '*' के समान है, तो −
    • यदि दूसरा '*' के समान है, तो −
      • dp[i] :=add(dp[i], mul(15, dp[i - 2]))
    • अन्यथा जब दूसरा <='6', तब −
      • dp[i] :=add(dp[i], mul(2, dp[i - 2]))
    • अन्यथा
      • dp[i] :=add(dp[i], mul(1, dp[i - 2]))
  • अन्यथा जब पहला '1' के समान हो या पहला '2' के समान हो, तो −
    • यदि दूसरा '*' के समान है, तो −
      • यदि पहला '1' के समान है, तो −
        • dp[i] :=add(dp[i], mul(9, dp[i - 2]))
      • अन्यथा जब पहला '2' के समान हो, तब −
        • dp[i] :=add(dp[i], mul(6, dp[i - 2]))
    • अन्यथा जब (प्रथम - '0') * 10 + (दूसरा - '0') <=26, तब -
      • dp[i] :=add(dp[i], dp[i - 2])
• रिटर्न डीपी[एन]

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   lli mul(lli a, lli b){
      return ((a % m) * (b % m)) % m;
   }
   int numDecodings(string s) {
      int n = s.size();
      vector <int> dp(n + 1);
      dp[0] = 1;
      if(s[0] == '0') return 0;
      dp[1] = s[0] == '*' ? 9 : 1;
      for(int i = 2; i <= n; i++){
         char first = s[i - 2];
         char second = s[i - 1];
         if(second == '*'){
            dp[i] = add(dp[i], mul(9, dp[i - 1]));
         }else if(second > '0'){
            dp[i] = dp[i - 1];
         }
         if(first == '*'){
            if(second == '*'){
               dp[i] = add(dp[i], mul(15, dp[i - 2]));
            }else if (second <= '6'){
               dp[i] = add(dp[i], mul(2, dp[i - 2]));
            }else{
               dp[i] = add(dp[i], mul(1, dp[i - 2]));
            }
         }else if(first == '1' || first == '2'){
            if(second == '*'){
               if(first == '1'){
                  dp[i] = add(dp[i], mul(9, dp[i - 2]));
               }else if(first == '2'){
                  dp[i] = add(dp[i], mul(6, dp[i - 2]));
               }
            }else if((first - '0') * 10 + (second - '0') <= 26){
               dp[i] = add(dp[i], dp[i - 2]);
            }
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numDecodings("2*"));
}

इनपुट

“2*”

आउटपुट

15