91. Decode Ways

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

Python

Bottom Up DP

from functools import cache


class Solution:
    def numDecodings(self, s: str) -> int:
        options = set([str(n) for n in range(1, 27)])

        @cache
        def dp(i: int):
            if i >= len(s):
                return 0
            if i == len(s)-1 and s[i:] in options:
                return 1

            count = 0
            if i == len(s)-2 and s[i:] in options:
                count += 1

            if s[i:i+2] in options:
                count += dp(i+2)
            if s[i:i+1] in options:
                count += dp(i+1)

            return count

        return dp(0)