[LeetCode] 91. Decode Ways

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

There are 2 ways to decode for each digit.

1. Treat this digit as a letter

2. Combine this digit and its adjacent digit then treat them as a letter

Use cache to memorize decoded ways of each digit

Time Complexity = O ( N )

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            if start == len(s):
                return 1
            
            # '0' cannot be leading digit
            if s[start] == '0':
                return 0
            
            # decode ways when treat s[i] as a letter 
            result = helper(start+1)
            
             # decode ways when treat s[i]s[i+1] as a letter
            if start + 1 < len(s)  and (s[start] == '1' or (s[start] == '2' and s[start+1] <= '6')):
                result += helper(start+2)
            
            return result
        
        return helper(0)
 

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = defaultdict(int)
        
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0
        
        for i in range(1, len(s)):
            
            if s[i] != '0':
                dp[i+1] = dp[i]
            
            if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
                dp[i+1] += dp[i-1]
        
        return dp[len(s)]

Edited on 07/11/2021. Simplify top-down and bottom-up solutions.