Leet Code 91. Decode Ways — Graphically Explained Python3 Solution

 

Photo by Michael Dziedzic on Unsplash

Problem 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. The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12203"
Output: 2
Explanation: It could be decoded as "ABTC" (1,2,20,3) or "LTC" (12,20,3).

Example 2:

Input: s = "20103"
Output: 1
Explanation: It could be decoded as "TJC" (20, 10, 3).

Example 3:

Input: s = "2030"
Output: 0
Explanation: 30 could be decoded.

Solution

Obvious Solution

The obvious (and brute force) way is to try every possible way. The solution looks like below tree and I will calculate final valid path number as the result. For example 1, it’s like a DFS way: first I can decode “1” or “12”, and then under “1”, I can have the choice of decoding “2” and “22”, and then under “2”, I can decode “2” only or “22” and etc. From below grahp, I can see there are some obvious duplicate calculations (like run into ‘0’ and ‘03’ decoding many times).

Best Solution (to me)

I can use Dynamic Programming to solve this. The idea comes from following thoughts: assuming there is a string X(for example, ‘12’) and I know the ways to decode it is 2 ([1,2] or [12]). Now let me append one more char(for example, ‘3’). Obviously, for the new string, the decode way is 2 (by decode 3 to ‘C’ and get [1,2,3] or [12,3]) + 1 (by decode 3 with its previous char ‘2’, and then use adopt the decode ways for ‘1’ which is 1) = 3. So in general, if I use dp[i] for the decode ways of the string ending at index i, I will have

dp[i] = dp[i-1] + dp[i-2] (if 0 < s[i-1] + s[i] ≤ 26)

Above is a raw idea and there are some details to figure out as below.

1. If s[i] is ‘0’, it must combine with its previous char since ‘0’ cannot be decoded; so in this case, there should be a previous char and it should be either ‘1’ or ‘2’. If s[i] is not ‘0’, then dp[i] = dp[i-1].
2. if dp[i] is 0, then I need to immediately return 0 which means it’s impossible to decode the whole string. Think about the example like ‘123012592329’, when I iterate to calculate dp[3], the ‘0’ (at index = 3) itself cannot be decoded and even it gets combined with previous char (‘3’), it cannot produce an valid decoded char and hence it makes no sense to continue.
3. To make sure dp[i-1] and dp[i-2] are always valid, I initiliaze dp=[1,1] and use dp[-1] and dp[-2] instead of dp[i-1] and dp[i-2]. The values of 1s assume there are always 1 way to decode (if not running to “return 0”).

Time & Space Complexity

It takes only one iteration of all input (assuming there are N letters) so the time complexity is O(N).

I use an array to store up to N+1 values (for an initialization value and decode ways of s[:0], s[:1], s[:2] and etc.) so the space needed is propotional to N and hence the space complexity is O(N) as well.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549