Chương trình giải mã một thông điệp nhất định trong C ++

Giả sử chúng ta được cung cấp một thông điệp được mã hóa là một chuỗi các số nguyên. Giờ đây, những số nguyên này có thể được ánh xạ tới một chữ cái cụ thể trong bảng chữ cái. a được ánh xạ tới 1, b được ánh xạ tới 2, c được ánh xạ tới 3, v.v. Ngoài ra còn có một ký tự '*' có thể có trong tin nhắn và có thể được ánh xạ tới bất kỳ số nào từ 1 đến 9. Vì vậy, với một 'đầu vào' thông báo, chúng ta phải tìm ra bao nhiêu cách nó có thể được giải mã.

Vì vậy, nếu đầu vào giống như input ="18", thì đầu ra sẽ là 2.

Tin nhắn có thể được giải mã thành "ah", 1 ánh xạ tới "a" và 8 ánh xạ tới "h". Ngoài ra, số có thể ánh xạ tới "r", 18 ánh xạ tới "r". Cho nên. có tổng cộng 2 cách mà đầu vào có thể được giải mã.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=độ dài của đầu vào
Xác định một mảng dynArr có kích thước:n + 1 và khởi tạo nó bằng các số 0
p:=1
k:='0'
dynArr [0]:=1
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- c:=input [i - 1]
- nếu c giống với 0 và không (k giống với '1' hoặc k giống với '2' hoặc k giống với '*'), thì -
  - p:=0
  - Ra khỏi vòng lặp
- nếu đầu vào [i - 1] giống với '*', thì -
  - dynArr [i]:=(dynArr [i - 1] * 9) mod m
  - nếu k giống với '1' hoặc k giống với '*', thì -
    - dynArr [i]:=(dynArr [i] + dynArr [i - 2] * 9) mod m
  - nếu k giống với '2' hoặc k giống với '*', thì -
    - dynArr [i]:=(dynArr [i] + (dynArr [i - 2] * 6) mod m) mod m
- nếu không,
  - nếu c không bằng '0', thì -
  - - nếu k giống với '1' hoặc k giống với '*', thì -
      - dynArr [i]:=(dynArr [i] + dynArr [i - 2]) mod m
    - if (k giống với '2' hoặc k giống với '*') và đầu vào [i - 1] <='6', thì -
      - dynArr [i]:=(dynArr [i] + (dynArr [i - 2]) mod m) mod m
- k:=c
nếu p khác 0 thì trả về dynArr [n], ngược lại trả về 0

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Chương trình giải mã một thông điệp nhất định trong C ++

Ví dụ

Đầu vào

Đầu ra