Bài 14.5. Giải Mã Thông Điệp Cổ Xưa - [Độ khó: Khó]

Một nhà khảo cổ học phát hiện ra một thông điệp được khắc trên đá cổ dưới dạng một chuỗi các chữ số. Họ tin rằng thông điệp được mã hóa bằng một quy tắc giải mã đặc biệt:

• Mỗi chữ số từ '1' đến '9' có thể được giải mã thành một chữ cái tương ứng ('1' thành 'A', '2' thành 'B', ..., '9' thành 'I').
• Một nhóm hai chữ số từ '10' đến '26' có thể được giải mã thành một chữ cái tương ứng ('10' thành 'J', '11' thành 'K', ..., '26' thành 'Z').
• Số '0' không thể được giải mã thành bất kỳ chữ cái nào.

Bạn được giao nhiệm vụ viết một chương trình để tìm tổng số cách khác nhau mà một chuỗi số cho trước có thể được giải mã thành một chuỗi các chữ cái.

INPUT FORMAT

Một dòng duy nhất chứa chuỗi \(S\) (\(1 \le |S| \le 40\)), chỉ bao gồm các chữ số từ '0' đến '9'.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số cách giải mã. Nếu chuỗi không thể giải mã được (ví dụ, có '0' không hợp lệ), kết quả là \(0\).

Ví dụ 1:

Input:

12

Output:

2

Giải thích: Chuỗi "12" có thể được giải mã theo 2 cách:

1. '1' -> 'A', '2' -> 'B'. Kết quả: "AB"
2. '12' -> 'L'. Kết quả: "L"

Ví dụ 2:

Input:

226

Output:

3

Giải thích: Chuỗi "226" có thể được giải mã theo 3 cách:

1. '2' -> 'B', '2' -> 'B', '6' -> 'F'. Kết quả: "BBF"
2. '2' -> 'B', '26' -> 'Z'. Kết quả: "BZ"
3. '22' -> 'V', '6' -> 'F'. Kết quả: "VF"

Ví dụ 3:

Input:

0

Output:

0

Giải thích: Chữ số '0' không thể giải mã được riêng lẻ, vì vậy không có cách nào.

Ví dụ 4:

Input:

101

Output:

2

Giải thích: Chuỗi "101" có thể được giải mã theo 2 cách:

1. '10' -> 'J', '1' -> 'A'. Kết quả: "JA"

2. '1' -> 'A', '0' không thể giải mã (không có chữ cái nào cho '0'), nhưng '0' có thể đi kèm với '1' để thành '10'. Chính xác hơn: '1' -> 'A', phần còn lại là "01". "01" không hợp lệ vì '0' đứng đầu. 101

   • Option 1 (decode '10'): '10' -> 'J'. Remaining: '1'. '1' -> 'A'. Total: "JA".
   • Option 2 (decode '1'): '1' -> 'A'. Remaining: '01'. This is invalid, as '0' cannot be decoded alone, and '01' is not a valid 2-digit code (must be 10-26). The correct paths are:
   1. 10 ('J') và 1 ('A') -> JA
   2. 1 ('A') và 0 (Invalid). Ah, the problem states '10' to '26' for 2-digit codes. '0' can only exist as part of '10' or '20'. So for "101":
   • Take '1' ('A'). Remaining "01".
     • Take '0' (invalid).
     • Take '01' (invalid 2-digit code).
   • Take '10' ('J'). Remaining "1".
     • Take '1' ('A'). So only 1 way: "JA". My example output says 2. Let's re-verify the common "decode ways" problem. "101" -> "JA" (10, 1) and "A_INVALID" (1, 01 is not a valid interpretation). Perhaps I should rephrase my "0" rule. If a '0' appears, it must be part of a '10' or '20' combination. If it's a standalone '0' or part of '01'-'09', it's invalid.

   Let's adjust example 4: Input:

   101

   Output:

   1

   Giải thích: Chuỗi "101".

   • Cách 1: Giải mã '10' thành 'J'. Chuỗi còn lại là '1', giải mã thành 'A'. Kết quả: "JA".
   • Cách 2: Giải mã '1' thành 'A'. Chuỗi còn lại là '01'.
     • Nếu cố gắng giải mã '0' một mình, không hợp lệ.
     • Nếu cố gắng giải mã '01' là một cặp, không hợp lệ vì chỉ có '10' đến '26' là hợp lệ. Vậy, chỉ có 1 cách giải mã duy nhất là "JA".