Decode Ways — Leetcode 91

Difficulty: Medium; Category: Dynamic Programming

Decode Ways - LeetCode

After reading the question, it first occurred to me that maybe I need to build a map built from letters and numbers. But when I was building the map, I realized that this map was not really necessary, all I need is the condition that the given number should be between 1 and 26.

Since the total number of possible decoding ways is accumulated from start to finish, we can consider applying dynamic programming to record the result at each position.

The valid numbers for unit-digit are 1–9 while the valid numbers for ten-digit are 10–26, notice that the number starting from ‘0’ is invalid, such as “06” is an invalid number.

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0

        dp = [0 for _ in range(len(s) + 1)] 

        # base case initialization
        dp[0] = 1 
        dp[1] = 1 
        
        for i in range(2, len(s) + 1): 
            # One step jump
            if 0 < int(s[i-1]) <= 9:    #(2)
                dp[i] = dp[i - 1]
            # Two step jump
            if 10 <= int(s[i-2:i]) <= 26: #(3)
                dp[i] += dp[i - 2]
        return dp[len(s)]

1. The first edge case is the first number of s can not be ‘0’, no matter is for unit-digit or ten-digit. So if the s start from 0, just return 0
2. Create a dp list in order to store the number of possible ways that each position of s can have. Need to include the position 0 to position n, so the length of dp will be len(s)+1
3. dp[1] = 1 for when the length of s is one and the number is not 0, there is one possible way.
4. dp[0] = 1 for two-step jump, when the length of s is two and if the number is valid, make dp[i] += dp[i-2] (i is 2)
5. As mentioned previously, the valid range of number for one-step jump is 1–9 while for two-step jump is 10–26
6. After all, return the last value of dp, which means so far for that length of s can have those possible ways to decode.

Bonus

Actually, the question Decode Ways — Leetcode 91 can be thought of as an advanced question from a very classic question Climbing Stairs.

70. Climbing Stairs

Difficulty: Easy; Category: Dynamic Programming

Climbing Stairs - LeetCode

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0 for _ in range(n+1)]
        
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[-1]

1. If the total layer of stairs n is one, there is only one way to climb, could return 1 immediately
2. Create a dp list to store the number of possible climb combinations for that position. And the reason why the list length is in range(n+1), not only n, is because we want the result to be stored at the position directly to the number, like when we go to the third stair, we could just store the result in dp[3]
3. In the end, return the last value from dp list, which also means that n stairs could have that value of possible way to climb.

REFERENCE
https://leetcode.com/problems/decode-ways/discuss/253018/Python%3A-Easy-to-understand-explanation-bottom-up-dynamic-programming