# 91 Decode Ways

A message containing letters from`A-Z`is 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.

![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIhdKCbc0plLc1IVp%2F91_decode_ways1.png?generation=1568003899586531\&alt=media)![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIhdMCvDFuf0dZuut%2F91_decode_ways2.png?generation=1568003906778992\&alt=media)![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIhdOhXvpB3inFbWt%2F91_decode_ways3.png?generation=1568003894709525\&alt=media)

**Complexity:** O(N) time and space

```python
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))
```