[LC] 91. 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 mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "111" can have each of its "1"s be mapped into 'A's to make "AAA", or it could be mapped to "11" and "1" ('K' and 'A' respectively) to make "KA". Note that "06" cannot be mapped into 'F' since "6" is different from "06".

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

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

Approach

I first thought that there is some combination because a list of numbers can be divided in some way. For example, within 226, we can get ‘2’, ‘2’, ‘6’ or ’22’, ‘6’ or ‘2’, ’26. It seems like a combination of a number of ways within n character. However, there is a serious limitation since we have conditions like decoded number must be between ‘A’ and ‘Z’.

I was trying to find some pattern but it was hard to find. Rather than find patterns, I found it is related to dynamic programming.

You can see the previous decoded way is related to the current decoded way. If my number is related to the previous number, for example, current = 6 and previous = 2, then current number is either the previous # of way or something. However, I can’t find the relation for about 1 hour! So, I tried to write down some equations to find the recurrence relation between them.

This was my initial recurrence relation. Assume we have an array of numbers that consist of c[1]c[2]….c[N]. For example, if the number is ‘2323’ then c[1] is 2, and c[N] is 3. Then, assume d[i] is decoded way at the digit of i. In the previous example, if we have ‘226’ then d[1] is 1 (only we have ‘B’) and d[2] is 2 (‘BB’ or ‘V’). Finally we have d[3] as 3 (‘BBB’ or ‘VB’ or ‘BZ’)

After this step, I finally found a recurrence relation. Let says the current digit position is ‘i’. If c[i] can be connected with c[i-1], we can bring d[i-2] since c[i-1]c[i] can be decoded as a single character. At the same time, we can bring d[i-1] since c[i] can be decoded as a single character.

Let’s see the above example. We know d[3]=3, d[2]=2, d[1]=1. How about d[4] when the current position is ‘4’? We first see c[4] is ‘1’ which cannot connect to c[3] which is ‘6’ since 61 is over the ‘Z’. So, there is probably no change and d[3] = d[2]. Next, when i is 5, c[5] is 1 which can be connected to c[4] which is 1. In case when c[4]c[5] (11), we can bring d[3]. When c[5] is used as single, we can bring d[4]. So, d[5] = d[4] + d[3].

How about the current digit is zero? In that case, 0 can be formed with the previous one if it is 1 or 2. Otherwise, it cannot be used as a single. So, we should bring d[i-2] only not d[i-2] + d[i-1].

To sum up, here is recurrence relation:

d[i+1] =
d[i-1] + d[i-2] if (c[i-1] == 1 and 0 <= c[i] <= 9) or (c[i-1] == 2 and 0 <= c[i] < 7) and c[i] is not 0
d[i-1] if (c[i-1] == 1 and 0 <= c[i] <= 9) or (c[i-1] == 2 and 0 <= c[i] < 7) and c[i] is 0
d[i] otherwise

(I can’t represent using piecewise function but I believe you can understand my intention!)

Solution

class Solution:
    def numDecodings(self, s: str) -> int:
        if len(s) == 0 or s[0] == '0':
            return 0
        
        d = [1,1]
        for i in range(1, len(s)):
            if s[i-1] == '0' and s[i] == '0':
                return 0
            if (s[i-1] == '1' and '0' <= s[i] <= '9') or (s[i-1] == '2' and  '0' <= s[i] < '7'):
                if s[i] == '0':
                    d.append(d[i-1])
                else:
                    d.append(d[i-1] + d[i])
            elif s[i] != '0':
                d.append(d[i])
            else:
                return 0
        return d.pop()
            

Submission

Runtime: 52 ms, faster than 9.76% of Python3 online submissions for Decode Ways.Memory Usage: 14.4 MB, less than 40.28% of Python3 online submissions for Decode Ways.

Time & Space Complexity: O(N)