Số cách giải mã (Decode Ways) trong Python

Giả sử chúng ta có một thông điệp chứa chữ cái từ A đến Z được mã hóa thành số theo ánh xạ sau: 'A' → 1, 'B' → 2 ... 'Z' → 26. Nếu chúng ta có một chuỗi không rỗng chỉ chứa chữ số, chúng ta phải tìm số cách mà chuỗi đó có thể được giải mã. Ví dụ, chuỗi "12" có thể tạo từ "AB" hoặc "L", nên có 2 cách. Câu trả lời là 2.

Để giải quyết, chúng ta làm theo các bước sau:

• Chúng ta sẽ giải quyết bằng quy hoạch động.
• n := độ dài s.
• dp := mảng với n số 0.
• Nếu s[0] không phải '0', thì dp[0] := 1.
• Với i từ 1 đến n-1:
  • x := s[i] dưới dạng số nguyên, y := chuỗi con của s từ chỉ số i-1 đến i+1 dưới dạng số nguyên.
  • Nếu x >= 1 và x <= 9, thì dp[i] := dp[i] + dp[i-1].
  • Nếu y >= 10 và y <= 26:
    • Nếu i-2 >= 0, thì dp[i] := dp[i] + dp[i-2], ngược lại tăng dp[i] lên 1.
• Trả về phần tử cuối của dp.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def numDecodings(self, s):
        n = len(s)
        dp = [0 for i in range(n)]
        if s[0] != '0':
            dp[0] = 1
        for i in range(1, n):
            x = int(s[i])
            y = int(s[i-1:i+1])
            if x >= 1 and x <= 9:
                dp[i] += dp[i-1]
            if y >= 10 and y <= 26:
                if i-2 >= 0:
                    dp[i] += dp[i-2]
                else:
                    dp[i] += 1
        return dp[-1]

ob1 = Solution()
print(ob1.numDecodings("226"))

Đầu vào

"226"

Đầu ra

3