LeetCode #91: Decode Ways
β’ 92 words β’ 1 min β’ updated
python
class Solution:
def numDecodings(self, s: str) -> int:
from functools import cache
@cache
def solve(n):
if n < 0:
return 1
if n == 0:
if s[n] in "123456789":
return 1
else:
return 0
ans = 0
# take one char, s[n]
if s[n] in "123456789":
ans += solve(n - 1)
# take two chars, s[n - 1] and s[n]
if s[n - 1] in "12" and 10 <= int(s[n - 1] + s[n]) <= 26:
ans += solve(n - 2)
return ans
return solve(len(s) - 1)