Leetcode 91. Decode Ways (Python)

Related Topic

Dynamic-Programming.

Description

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Sample I/O

Example 1

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Methodology

This question solved by Dynamic Programming. It is similar with question 70 Climbing Stairs. For climbing stair qusetion, each time you can either climb 1 or 2 steps and in this question, each combination of the number must in range 1 and 26 inclusive, so that means for each combination, it has to be 1 digit or 2 digits.

1. Before we find the pattern, there are some special case need to consider, if the combination is less than 1 it is invalid, if is is greater than 26, for example 27, we can not find the matched letter for that, so we can only split it to 2 and 7. For 0, there are only two case will be valid, 10 and 20.

2. Now we find the base case (with valid number)
   1. If there is only 1 digit, then there is only 1 combination The base case will be:

      dp[0]=1,
      

3. Find the pattern: (with valid number for example 22226)
   1. 2: [2]
   2. 22: [2,2],[22]
   3. 222: [2,2,2],[22,2],[2,22]
   4. 2222: [2,2,2,2],[22,2,2],[2,22,2],[2,2,22],[22,22]
   5. 22226:[2,2,2,2,6],[22,2,2,6],[2,22,2,6],[2,2,22,6],[2,2,22,6],[22,22,6],[2,2,2,26],[22,2,26],[2,22,26]

   Based the climbing stair question, for each move we have either 1 steps or 2 steps, we focus on last two moves, same here! Plus, we need to identify each combination is invalid. Now, the key point to identify each combination is determined by position of ‘0’.

   1. If the last digit is not ‘0’, then there are at least dp[i-1] ways. Based on the pattern above. This is first identification.
   2. Now, we check last two digits. If the last two digit is in greater than ‘09’ and smaller than ‘27’, based on the above pattern, we will add the total ways of step before the last step.

Note

Some hide case:

1. leading ‘0’ will return 0
2. consective ‘0’ will return 0

Code

def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        for i in range(1, len(dp)):
            if int(s[i-1]) != 0:
                dp[i] = dp[i-1]
            if i != 1 and '09' < s[i-2:i] < '27':
                dp[i] += dp[i-2]
        return dp[-1]

BigO

We iterate all dp array, it will cost O(n+1), each value will add up last two value as result, it will cost (1+2), in total will be O((n+1)+2(n+1)) and It is O(n)