202402031953
tags: #dp

from functools import lru_cache

class Solution:
	def isValidNum(self, num):
		return 1 <= num <= 26
	def numDecodings(self, s: str) -> int:
		@lru_cache(maxsize=None)
		def solve(i):
			if i == 0 or i == 1:
				return 1 if int(s[0]) != 0 else 0
			num1 = int(s[i - 1:i])
			num2 = int(s[i - 2:i])
			res = 0
			if self.isValidNum(num1):
				res += solve(i - 1)
			if self.isValidNum(num2) and s[i - 2] != "0":
				res += solve(i - 2)
			return res
		return solve(len(s))

Reference

https://leetcode.com/problems/decode-ways/