Problem statement

https://binarysearch.com/problems/Decode-Message/

Solution

Equal to Leetcode 0091. Decode Ways.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        @lru_cache(None)
        def dp(i):
            if i == -1: return 1
            ans = 0
            if s[i] > "0": ans += dp(i-1)
            if i >= 1 and "10" <= s[i-1:i+1] <= "26":
                ans += dp(i-2)
            return ans
        
        return dp(len(s) - 1)