[LeetCode] 639. Decode Ways II

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

The top-down solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            """
            total decoding way of s[start:]
            """
            
            if start == len(s):
                return 1
            
            # '0' cannot be the leading digit
            if s[start] == '0':
                return 0
            
            # total decoding way when consider s[start] is a letter
            result = (9 if s[start] == '*' else 1) * helper(start + 1)
            
            # total decoding way when consider s[start]s[start+1] is a letter 
            if start + 1 < len(s):
                if s[start] == '1':
                    if s[start+1] != '*':
                        result += 1 * helper(start + 2)
                    else:
                        # s[start+1] == '*'
                        result += 9 * helper(start + 2)
                elif s[start] == '2':
                    if '0' <= s[start+1] <= '6':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += 6 * helper(start + 2)
                elif s[start] == '*':
                    if '0' <= s[start+1] <= '6':
                        result += 2 * helper(start + 2)
                    elif '7' <= s[start+1] <= '9':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += (9 + 6) * helper(start+2)
            
            return result % (10 ** 9 + 7)
         
        return helper(0)

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        M = 10 ** 9 + 7
        N = len(s)
        
        if s[0] == '0': return 0
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else 1
        
        for i in range(1, N):
            if s[i] == '*':
                dp[i+1] = 9 * dp[i] % M
                
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + 9 * dp[i-1]) % M
                elif s[i-1] == '2':
                    dp[i+1] = (dp[i+1] + 6 * dp[i-1]) % M
                elif s[i-1] == '*':
                    dp[i+1] = (dp[i+1] + 15 * dp[i-1]) % M
            else:
                dp[i+1] = dp[i] if s[i] != '0' else 0
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '2' and s[i] <= '6':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '*':
                    if s[i] <= '6':
                        dp[i+1] = (dp[i+1] + 2 * dp[i-1]) % M
                    else:
                        dp[i+1] = (dp[i+1] + dp[i-1]) % M
        
        return dp[N]