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

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

เช่น หาก input เป็น "18" ผลลัพธ์จะเป็น 2

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

ขั้นตอนการแก้ปัญหา

• n := ความยาวของ input
• สร้างอาเรย์ dynArr ขนาด n+1 และกำหนดค่าเริ่มต้นเป็น 0
• p := 1
• k := '0'
• dynArr[0] := 1
• วนลูป i จาก 1 ถึง n:
  • c := input[i - 1]
  • ถ้า c เป็น '0' และ k ไม่ใช่ '1', '2', หรือ '*' แล้ว:
    • p := 0
    • ออกจากลูป
  • ถ้า input[i - 1] เป็น '*':
    • dynArr[i] := (dynArr[i - 1] * 9) mod m
    • ถ้า k เป็น '1' หรือ '*': dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
    • ถ้า k เป็น '2' หรือ '*': dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
  • กรณีอื่น:
    • ถ้า c ไม่ใช่ '0': dynArr[i] := dynArr[i - 1]
    • ถ้า k เป็น '1' หรือ '*': dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
    • ถ้า (k เป็น '2' หรือ '*') และ input[i - 1] <= '6': dynArr[i] := (dynArr[i] + dynArr[i - 2]) 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;       }       k = c;    }    return p ? dynArr[n] : 0; } int main() { cout << solve("18") << endl; return 0; }

อินพุต

18

เอาต์พุต

2