Description of the Problem

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Code

class Solution: def numDecodings(self, s: str) -> int: @lru_cache(None) def dp(i): if i == len(s): return 1 ans = 0 if s[i] != '0': ans += dp(i+1) if s[i] == '1' and i+1< len(s): ans += dp(i+2) if s[i] == '2' and i+1 < len(s) and s[i+1] <= '6': ans += dp(i+2) return ans return dp(0) 

Link To The LeetCode Problem

LeetCode