Decode Ways

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 test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Intuition

For this question, the best way is to manually go through one example first.

• One example for happy scenario
• One example for unhappy/edge cases

We define a number is convertible if it's within the range of 1 -> 26

Happy scenario

Let's say as of happy example, we have 123. Let's try to walk through this number

1. First, to parse 123, we need to parse the 1 in 123.
   • The number of way to parse 1 is 1
2. Next, we want to parse 12 in 123.
   • In order to parse 12, it's parse(1)2 and parse(12)
     • The number of way to parse 1 is 1. Therefore we can make 1 way
     • But 12 can also parse by itself. So we +1 to our number of ways, so 2 ways
3. Next, we want to parse 123 in 123.
   • In order to parse 123, it's parse(12)3 and parse(1)23
     • parse(12) is the above so it's just 2
     • parse(1) is also the above so it's just 1
     • So it's basically 3

As we can see, for the happy scenario, we have the formula:

if isConvertible(i) and isConvertible(i - 1 : i + 1):
	result[i] = result[i - 1] + result[i - 2]

Unhappy scenario

Let's consider the scenario 2101

1. The number of way to parse(2) is 1
2. We want to parse 21 which can be parse(2)1 and parse(21). So it's 2
3. We want to parse 210:
   • We cannot do parse(21)0 since 0 is invalid number. Therefore we can only do parse(2)10. Which is dp[i - 2] = 1
4. We want to parse 2101:
   • We can do parse(210)1 but not parse(21)01 since 01 is not a valid number. Therefore we choose parse(210) which is dp[i - 1] = 1

So we have another formula:

if isConvertible(i) but not isConvertible(i - 1):
	result[i] = result[i - 1]

if not isConvertible(i) but isConvertible(i-1):
	result[i] = result[i - 2]
	
else:
	# As of the question, if it's invalid return 0
	return 0

Identify 1-D or 2-D array

As a result, this is similar to House Robbery of fibonnaci pattern. Therefore we can use 1-D array.

It's important to note that the calculation can start at the second index already. For example 10, we need to calculate at 0 already so we can shift everything to the right by 1

So for example if we have number 10 our dp array will be:

  1 0
1,1,1

Where we initialise the first element is 1, the reason why it's 1 and not 0 is because in the case of happy scenario, for example

  1,1
1,1,2

We can still follow the same formula and has 2

Implementation

class Solution:
    def numDecodings(self, s: str):
        if (s[0] == "0"): return 0

        dp = [0 for _ in range(len(s) + 1)]
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, len(s) + 1):
            canConvertThisNumber = self.isConvertible(s[i - 1])

            # Since everything is shifted to the right, we - 1 to get the value of S
            canConvertThisAndPreviousNumberMerged = self.isConvertible(s[(i - 1) - 1: (i + 1) - 1])

            if canConvertThisNumber and canConvertThisAndPreviousNumberMerged:
                dp[i] = dp[i - 2] + dp[i - 1]
            elif canConvertThisNumber and not canConvertThisAndPreviousNumberMerged:
                dp[i] = dp[i - 1]
            elif not canConvertThisNumber and canConvertThisAndPreviousNumberMerged:
                dp[i] = dp[i - 2]
            else:
                return 0
        
        return dp[len(s)]
    
    def isConvertible(self, s):
        if s[0] == "0": return False
        num = int(s)

        return num >= 1 and num <= 26

Time complexity: $O(n)$
Space complexity: $O(n)$ — could be optimise to $O(2)$ by using 2 variables only. See House Robbery > Optimisation