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 L
.
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 26
.
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.
class Solution:
def numDecodings(self, s: str) -> int:
mem = {}
def inner(s):
if s in mem:
return mem[s]
if s == "":
return 1
if s[0] == '0':
return 0
if len(s) >= 2 and s[:2] <= '26':
mem[s] = inner(s[1:]) + inner(s[2:])
return mem[s]
else:
mem[s] = inner(s[1:])
return mem[s]
return inner(s)
if __name__ == '__main__':
s = Solution().numDecodings
print(s('11106'), 2)
print(s('06'), 0)
print(s('12'), 2)
print(s('226'), 3)
print(s("2611055971756562"), 4)
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.