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. Các số nguyên này có thể được ánh xạ đến các chữ cái cụ thể trong bảng chữ cái: a được ánh xạ đến 1, b đến 2, c đến 3, và cứ như vậy. Ngoài ra, còn có ký tự '*' có thể xuất hiện trong thông điệp và có thể được ánh xạ đến bất kỳ số nào từ 1 đến 9. Cho một thông điệp 'input', chúng ta phải tìm ra số cách mà nó có thể được giải mã.
Ví dụ, nếu input là "18", thì kết quả sẽ là 2.
Thông điệp có thể được giải mã thành "ah", vì 1 ánh xạ đến "a" và 8 ánh xạ đến "h". Ngoài ra, số 18 cũng có thể ánh xạ đến "r". Vì vậy, tổng cộng có 2 cách để giải mã đầu vào.
Giải thuật
Để giải quyết bài toán này, chúng ta thực hiện các bước sau:
- n := độ dài của input
- Định nghĩa mảng dynArr kích thước n+1 và khởi tạo với giá trị 0
- p := 1
- k := '0'
- dynArr[0] := 1
- Vòng lặp i từ 1 đến n:
- c := input[i - 1]
- Nếu c là '0' và k không phải là '1', '2', hoặc '*', thì p := 0 và thoát khỏi vòng lặp
- Nếu input[i - 1] là '*':
- dynArr[i] := (dynArr[i - 1] * 9) mod m
- Nếu k là '1' hoặc '*': dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
- Nếu k là '2' hoặc '*': dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
- Ngược lại:
- Nếu c khác '0': dynArr[i] := dynArr[i - 1]
- Nếu k là '1' hoặc '*': dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
- Nếu (k là '2' hoặc '*') và input[i - 1] <= '6': dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
- k := c
- Nếu p khác 0, trả về dynArr[n], ngược lại trả về 0
Ví dụ minh họa
#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;
}
Đầu vào
18
Đầu ra
2