Chương trình đếm số cách giải mã thông điệp trong Python

Cho ánh xạ 'a'=1, 'b'=2, ..., 'z'=26 và chuỗi mã hóa message, đếm số cách giải mã.

Ví dụ

Đầu vào: message = "222".
Đầu ra: 3 (giải mã: "bbb", "bv", "vb").

Thuật toán

1. Khởi tạo mảng memo kích thước len(message)+1 toàn 0.
2. memo[0] = 1, memo[1] = 1 nếu message[0] != '0' else 0.
3. Với i từ 2 đến len(message):
   • n1 = int(message[i-1:i]), n2 = int(message[i-2:i]).
   • n1_valid = n1 > 0, n2_valid = 10 <= n2 <= 26.
   • Nếu n1_valid: memo[i] += memo[i-1].
   • Nếu n2_valid: memo[i] += memo[i-2].
4. Trả về memo[-1].

Mã nguồn Python

class Solution:
    def solve(self, message):
        memo = [0] * (len(message) + 1)
        memo[0] = 1
        memo[1] = 1 if message[0] != "0" else 0
        for i in range(2, len(message) + 1):
            n1 = int(message[i-1:i])
            n2 = int(message[i-2:i])
            n1_valid = n1 > 0
            n2_valid = 10 <= n2 <= 26
            if n1_valid:
                memo[i] += memo[i-1]
            if n2_valid:
                memo[i] += memo[i-2]
        return memo[-1]

ob = Solution()
print(ob.solve("2223"))

Đầu vào / Đầu ra

Input: "2223"
Output: 5