Problem statement

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

Solution

Classical dynamic programming problem, where we need to carefully connect dp_new with dp. There is more clean solution, if we keep 3 states: dp[0] is number of total ways,dp[1] is number of decodes, ending with 1, which is not used yet and dp[2] is number of decodes, ending with 2, which is not used yet. Then we can do the following recursion:

  1. If c == "*" then there can be two options: if last number has only one digit, then we have 9*dp[0] options. Also, if we try go group last two digits, we have 9*dp[1] options for ...1* case and 6*dp[2] options for ...2* case. To evaluate new dp[1] and dp[2], we just return dp[0].
  2. If c != "*" then total number of options is (c > '0') * dp[0] for single digit last number or we could pair it with 1 or with 2 if it is not more than 6. To evaluate new dp[1], we check if last digit is 1 and for dp[2], we check if last digit is 2.

Complexity

Time complexity is O(n), space complexity is O(1).

Code

class Solution(object):
    def numDecodings(self, S):
        mod, dp = 10**9 + 7, [1, 0, 0]
        for c in S:
            dp_new = [0,0,0]
            if c == '*':
                dp_new[0] = 9*dp[0] + 9*dp[1] + 6*dp[2]
                dp_new[1] = dp[0]
                dp_new[2] = dp[0]
            else:
                dp_new[0]  = (c > '0') * dp[0] + dp[1] + (c <= '6') * dp[2]
                dp_new[1]  = (c == '1') * dp[0]
                dp_new[2]  = (c == '2') * dp[0]
            dp = [i % mod for i in dp_new]
        return dp[0]

Solution 2

Previous solution is very fast and efficient, but I think it is a bit difficult to invent it in short time. So, here is an alternative: let dp(i) be the number of ways to decode s[:i]. Then we can have several cases:

  1. if i < 0, we return 1, there is only one way to decode empty string.
  2. if s[i] == *, then there is 9*dp(i-1) ways to decode if we take last number 1-digit. To decode last number 2-digit we need to consider several cases. If we have 1*, then we have 9 ways to replace * with [1, 2, ..., 9]. If we have 2*, then we have 6 ways to replace it with [1, 2, ..., 6]. Finally, if we have **, then we have 15 options: [11, ...., 19, 21, ..., 26].
  3. if s[i] != *, that it it is digit, we have dp(i-1) ways to decode if we have last digit not equal to 0 and 0 ways if it is zero. For last 2 digits we need again consider cases: if previous element is digit, then only case [10, ..., 26] will be good for as, so we add dp(i-2). If we have *., then if . = 0, 1, 2, 3, 4, 5, 6, then we have 2 options for *: 1 and 2, in other case we have only one option.

Complexity

It is O(n) for time and space.

Code

class Solution: 
    def numDecodings(self, s):
        M = 10**9 + 7 
        
        @lru_cache(None)
        def dp(i):
            if i < 0: return 1
            if s[i] == "*":
                corr = {"1": 9, "2": 6, "*":15}
                ans = 9*dp(i-1)
                if i > 0: ans += corr.get(s[i-1], 0)*dp(i-2)
                return ans % M
            
            ans = dp(i-1) if s[i] != "0" else 0
            if i > 0 and "10" <= s[i-1:i+1] <= "26":
                ans += dp(i-2)
            elif i > 0 and s[i-1] == "*":
                ans += (2 if s[i] <= "6" else 1)*dp(i-2)
           
            return ans % M
        
        return dp(len(s)-1) % M