สมมติว่ามีการแมป 'a' = 1, 'b' = 2, ... 'z' = 26 และมีข้อความเข้ารหัส message string เราต้องนับจำนวนวิธีที่สามารถถอดรหัสได้
เช่น ถ้าอินพุตคือ message = "222" ผลลัพธ์จะเป็น 3 เนื่องจากถอดรหัสได้ 3 วิธี: bbb, bv, vb
ขั้นตอนการแก้ปัญหา
- memo := รายการ 0 ขนาดเท่ากับความยาว message + 1
- memo[0] := 1
- memo[1] := 1 ถ้า message[0] ไม่ใช่ "0" มิฉะนั้น 0
- for i ในช่วง 2 ถึงขนาดของ message ทำ
- n1 := ค่าตัวเลขของ message[i-1:i]
- n2 := ค่าตัวเลขของ message[i-2:i]
- n1_valid := true ถ้า n1 > 0
- n2_valid := true ถ้า n2 > 9 และ n2 < 27
- ถ้า n1_valid memo[i] := memo[i] + memo[i-1]
- ถ้า n2_valid memo[i] := memo[i] + memo[i-2]
- คืนค่าองค์ประกอบสุดท้ายของ memo
ตัวอย่างโค้ด
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))
อินพุต
"2223"
เอาต์พุต
5
