Giả sử chúng ta có ánh xạ như 'a' =1, 'b' =2, ... 'z' =26, và chúng ta có một chuỗi thông báo tin nhắn được mã hóa, chúng ta phải đếm số cách nó có thể được giải mã.
Vì vậy, nếu đầu vào là message ="222", thì đầu ra sẽ là 3, vì Điều này có thể được giải mã theo 3 cách:bbb, bv và vb.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
memo:=danh sách các 0 có kích thước giống như kích thước thư + 1
-
bản ghi nhớ [0]:=1
-
memo [1]:=1 khi thông báo [0] không giống với "0", ngược lại là 0
-
đối với tôi trong phạm vi từ 2 đến kích thước của tin nhắn, hãy làm
-
n1:=giá trị số của thông báo [từ chỉ mục i-1 đến i]
-
n2:=giá trị số của thông báo [từ chỉ mục i-2 đến i]
-
n1_valid:=true khi n1> 0
-
n2_valid:=true khi n2> 9 và n2 <27
-
nếu n1_valid là true thì
-
memo [i]:=memo [i] + memo [i-1]
-
-
nếu n2_valid là true thì
-
memo [i]:=memo [i] + memo [i-2]
-
-
-
trả về phần tử cuối cùng của bản ghi nhớ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, message): memo = [0 for i in range(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= n2>9 and n2<27 if n1_valid: memo[i]+=memo[i-1] if n2_valid: memo[i]+=memo[i-2] return memo[-1] ob = Solution() message = "2223" print(ob.solve(message))
Đầu vào
"2223"
Đầu ra
5