โปรแกรมถอดรหัสข้อความที่กำหนดใน C++

สมมติว่าเราได้รับข้อความเข้ารหัสที่เป็นสตริงของตัวเลขจำนวนเต็ม ตอนนี้ ตัวเลขจำนวนเต็มเหล่านี้สามารถจับคู่กับตัวอักษรที่ระบุในตัวอักษรได้ a ถูกจับคู่กับ 1, b ถูกจับคู่กับ 2, c ถูกแมปกับ 3, และอื่นๆ นอกจากนี้ยังมีอักขระ '*' ที่สามารถอยู่ในข้อความและสามารถจับคู่กับตัวเลขใดก็ได้ตั้งแต่ 1 ถึง 9 ดังนั้นเมื่อได้รับข้อความ 'อินพุต' เราต้องหาว่าสามารถถอดรหัสได้กี่วิธี

ดังนั้น หากอินพุตเหมือนกับอินพุต ="18" เอาต์พุตจะเป็น 2

ข้อความสามารถถอดรหัสเป็น "ah" ได้ เนื่องจาก 1 แผนที่เป็น "a" และ 8 แผนที่เป็น "h" นอกจากนี้ ตัวเลขยังสามารถจับคู่กับ "r" เนื่องจาก 18 จับคู่กับ "r" ดังนั้น. สามารถถอดรหัสอินพุตได้ทั้งหมด 2 วิธี

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

n :=ความยาวของอินพุต
กำหนดขนาดอาร์เรย์ dynArr:n+1 และเริ่มต้นด้วยศูนย์
p :=1
k :='0'
dynArr[0] :=1
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- c :=input[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 ม.
  - ถ้า k เหมือนกับ '2' หรือ k เหมือนกับ '*' ดังนั้น −
    - dynArr[i] :=(dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
- มิฉะนั้น
  - ถ้า c ไม่เท่ากับ '0' แล้ว −
  - - ถ้า k เหมือนกับ '1' หรือ k เหมือนกับ '*' ดังนั้น −
      - dynArr[i] :=(dynArr[i] + dynArr[i - 2]) mod ม.
    - ถ้า (k เหมือนกับ '2' หรือ k เหมือนกับ '*') และอินพุต[i - 1] <='6' ดังนั้น −
      - dynArr[i] :=(dynArr[i] + (dynArr[i - 2]) mod m) 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) % m;
      }
      k = c;
   }
   return p ? dynArr[n] : 0;
}

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

โปรแกรมถอดรหัสข้อความที่กำหนดใน C++

ตัวอย่าง

อินพุต

ผลลัพธ์