91 Decode Ways

A message containing letters fromA-Zis being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message"12", it could be decoded as"AB"(1 2) or"L"(12).

The number of ways decoding"12"is 2.

The Idea: This problem can be reduced to solving subproblems. For example, the input 12345 can be reduced to solving numDecodings(12345) = numDecodings(1234) + numDecodings(123) . The way to interpret this is that the tail end of the input 5 and 45 can interpreted to have two unique encodings. In this case of course, 45 would return 0 because it is out of bounds of the alphabetical mapping [1-26]. There are also a few other edge cases to consider, and I have highlighted then in the recursion trees below. The general idea is to not descend down a subtree if the interpretation of the tail end of the string isn't valid.

You may also notice some reoccurring subtrees, in which case, we use memiozation to save their results.

Complexity: O(N) time and space

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """

        if not s:
            return 0

        # memoization
        memo = {}

        # helper DFS (preorder)
        def __numDecodings(s, n):
            # if the front string is empty return 1 (leaf node in tree)
            if not s:
                return 1
            # check if in memory
            elif s in memo:
                return memo[s]
            # otherwise perform recursion
            else:
                # only decend down tree if we can at least get empty string from s
                result1, result2 = 0, 0
                if n:
                    # car and cdr
                    front1 = s[0:n - 1]
                    tail1 = s[n - 1:]

                    # there is no way to interpret 0 as a valid answer
                    result1 = 0 if tail1 == '0' else __numDecodings(front1, n - 1)
                if n-1:
                    # same idea, but now interpret 2 digits
                    front2 = s[0:n - 2]
                    tail2 = s[n - 2:]

                    # there is no way to interpret a valid solution if the
                    # number exceeds 26, or if the tail starts with 0 (consider edge case '101')
                    result2 = 0 if not (1 <= int(tail2) <= 26) or tail2[0] == '0' else __numDecodings(front2, n - 2)
                memo[s] = result1 + result2
                return memo[s]

        return __numDecodings(s, len(s))