Leetcode: Decode ways
Characters can be encoded via different numbers.
A -> 1, B -> 2, ..., Z -> 26. Given a string
s of numbers, return the number of possible decodings. For example
12 can be decoded as
A,B and as
We can look at this problem as a recursive problem. By checking the first two characters of each string, we can see if we decode it in zero, one or two ways. It is impossible to decode a string if it starts in
0, according to the rules. In this case we can return immediately and do not need to proceed further.
Next, we test if the string is at least
2 long. If this is the case we can either decode it as a single character or as two characters. The exception for two characters is that the number has to be below or equal to
Lastly, it is a good idea to add memoization to the algorithm and avoid performing the same operation twice. For example if we have a string of length 4:
1-1-1-1, we can decode it as
11-... or as
1-1.... However, the number of ways the remainder can be decoded stays the same.
Runtime: 74 ms, faster than 8.01% of Python3 online submissions for Decode Ways. Memory Usage: 14.3 MB, less than 6.92% of Python3 online submissions for Decode Ways.