ถอดรหัสวิธีที่ II ใน C ++

สมมติว่ามีข้อความที่มีตัวอักษรจาก A-Z ถูกเข้ารหัสเป็นตัวเลขโดยใช้วิธีการจับคู่ดังต่อไปนี้ -

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

ตอนนี้สตริงที่เข้ารหัสยังสามารถมีอักขระ '*' ซึ่งสามารถถือเป็นตัวเลขตั้งแต่ 1 ถึง 9 ได้ ดังนั้นหากเรามีข้อความที่เข้ารหัสซึ่งมีตัวเลขและอักขระ '*' เราก็ต้องหา จำนวนวิธีถอดรหัสทั้งหมด ถ้าคำตอบยาวมาก เราสามารถใช้ mod 109 + 7 เพื่อให้ได้ผลลัพธ์สุดท้าย ดังนั้นหากอินพุตเป็นเพียง * อาจเป็นไปได้ 9 วิธี ทั้งหมดนี้คือตัวเลขตั้งแต่ 1 ถึง 9 ดังนั้นนี่คือ A ถึง I

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน add() ซึ่งจะใช้ a, b,
• ผลตอบแทน ((a mod m) + (b mod m)) mod m
• กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,
• ผลตอบแทน ((a mod m) * (b mod m)) mod m
• จากวิธีหลัก ให้ทำดังนี้ -
• n :=ขนาดของ s
• กำหนดอาร์เรย์ dp ขนาด n + 1
• dp[0] :=1
• ถ้า s[0] เหมือนกับ '0' แล้ว −
  • คืน 0
• dp[1] :=9 เมื่อ s[0] เหมือนกับ ' * ' มิฉะนั้น 1
• สำหรับการเริ่มต้น i :=2 เมื่อฉัน <=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*”

ผลลัพธ์

15