Decode number of ways

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Input

• 1 <= s.length <= 100
• s, the string input, contains only digits and may contain leading zero(s).

Approach

This is a dynamic programming problem because the results of a previously decoded subproblem can contribute to solve the current subproblem.

I am personally not a big fan of this problem because the decoding part can be really confusing at the implementation level when trying to re-use previous results. A clean approach to decoding delivers the best results. The clearest way to solve this problem is to do the following:

1. Cover the first two base cases
   
   • For subproblem of size 0, what is the number of ways to decode? - This is naturally 1
   • For subproblem of size 1, what is the number of ways to decode? - If the first digit in s is 0 then this would be 0. For any other digit, we have a mapping, so we would have a 1.
2. Loop through each character in s, starting from index 2
   
   • If the current digit, i.e. "ones" digit is greater than 1, we'll re-use the answer for the previous subproblem i-1. This is the typical case where the number of ways to decode doesn't actually increase or decrease because the digit itself just has one mapping that we can add in a straightforward manner.
   • For example, adding 3 to 12 means going from [AB, L] to [ABC, LC], which is still 2 ways to decode.
   • If we look at the previous digit also and combine together to form a "double digit", and it happens to be within the range of 10-26, then we have a special mapping for it, so we'll also add the 2nd previous subproblem i-2 to the current results. This is because we want to combine the two different ways to decode - one from the additional mapping between digits 10-26 (i.e. 11 = K) and also one for the single digits (5 = E).

Solution

    def numDecodings(self, s: str) -> int:        
        results = []

        dp = [0] * (len(s) + 1)

        dp[0] = 1
        dp[1] = 1 if s[0] != "0" else 0

        if s[0] == "0" and len(s) == 1:
            return 0

        for i in range(2, len(s) + 1):
            one_digit = int(s[i-1])
            two_digits = int(s[i-2:i])

            if one_digit >= 1:
                dp[i] += dp[i-1]

            if 9 < two_digits < 27:
                dp[i] += dp[i-2]

        return dp[-1]