C++-এ দ্বিতীয় উপায় ডিকোড করুন

ধরুন একটি বার্তা আছে, যেটিতে A-Z থেকে অক্ষর রয়েছে যা নিম্নলিখিত ম্যাপিং পদ্ধতি ব্যবহার করে সংখ্যাগুলিতে এনকোড করা হচ্ছে -

'A' -> 1, 'B' -> 2, ... , 'Z' -> 26

এখন, এনকোড করা স্ট্রিংটিতে '*' অক্ষরও থাকতে পারে, যেটিকে 1 থেকে 9 পর্যন্ত সংখ্যার একটি হিসাবে গণ্য করা যেতে পারে। তাই যদি আমাদের কাছে এনকোড করা বার্তাটি সংখ্যা এবং অক্ষর '*' থাকে, তাহলে আমাদের খুঁজে বের করতে হবে এটি ডিকোড করার মোট উপায়। যদি উত্তরটি খুব দীর্ঘ হয়, আমরা চূড়ান্ত ফলাফল পেতে mod 109 + 7 ব্যবহার করতে পারি। সুতরাং যদি ইনপুট শুধুমাত্র * হয়, তাহলে 9টি সম্ভাব্য উপায় হতে পারে, এগুলি হল 1 থেকে 9 পর্যন্ত সংখ্যা, তাই এগুলি হল A থেকে I৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন অ্যাড() সংজ্ঞায়িত করুন, এটি a, b,
রিটার্ন ((a mod m) + (b mod m)) mod m
একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,
রিটার্ন ((a mod m) * (b mod m)) mod m
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
n :=s এর আকার
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])
রিটার্ন dp[n]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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*”

C++-এ দ্বিতীয় উপায় ডিকোড করুন

উদাহরণ

ইনপুট

আউটপুট