Problem statement

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

Solution 1

Let us use dynamic programming for this problem, where we keep 3 values on each step:

  1. dp[0] is total numbers to decode number s[:i].
  2. dp[1] is number of ways to decode number s[:i], if it ends with 1 and last digit is part of 2-digit number. This is important point.
  3. dp[2] is number of ways to decode number s[:i], if it ends with 2 and last digit is part of 2-digit number.

Now, we need to understand how to update our numbers:

  1. For dp_new[0] we can have 3 options: if last digit is more than 0, than we can take it as 1-digit number (by definition each part is number between 1 and 26). Also, we can take last number as 2-digit number if it starts with 1: this is exactly dp[1]. and if it starts with 2 and last digit is less or equal to 6.
  2. For dp_new[1] we have only one option: we need to have last symbol equal to 1.
  3. Similar for dp_new[2], we need to have last symbol equal to 2.

Complexity: time complexity is O(n): we iterate over each symbol once. Space complexity is O(1).

class Solution:
    def numDecodings(self, s):
        dp = [1, 0, 0]
        for c in s:
            dp_new = [0,0,0]
            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 = dp_new
        return dp[0]

Solution 2

In this problem we can see some repeating subproblems, so we can apply dynamic programming.

Let dp(i) is number of ways to decode string s[:i]. Then we can have the following cases:

  1. if i == -1, we return 1, because there is unique way to decode empty string.
  2. If last digit is not equal to 0, we need to add dp(i-1) to our answer.
  3. If last two digits form number from 10 to 26, we can use last 2 symbols for decoding, so we add dp(i-2) to our answer.

Complexity

Time complexity is O(n), we have n states and at most 2 transactions from one to another. Space complexity is O(n) as well.

Code

class Solution:
    def numDecodings(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)

Remark

If you like the solution, you can upvote it on leetcode discussion section: Problem 0091 Problem 0091