Giải mã các cách trong Python

Giả sử chúng ta có một tin nhắn chứa các chữ cái từ A đến Z đang được mã hóa thành các số bằng cách sử dụng ánh xạ sau - 'A' → 1, 'B' → 2 ... 'Z' → 26. Vì vậy, nếu chúng ta có một chuỗi không rỗng, chỉ chứa các chữ số, thì chúng ta phải tìm xem có bao nhiêu cách có thể được giải mã. Vì vậy, nếu chuỗi giống như "12", thì chuỗi đó có thể được tạo từ "AB" hoặc "L", vì vậy có hai cách khả thi. Vì vậy, câu trả lời sẽ là 2.

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

• Chúng tôi sẽ giải quyết vấn đề này bằng lập trình động.
• n:=độ dài của s
• dp:=một mảng có n số 0
• nếu s [0] không phải là '0', thì dp [0]:=1
• cho tôi trong phạm vi 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à y <=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], nếu không thì tăng dp [i] lên 1
• trả về phần tử cuối cùng của dp

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau đây để 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