# 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.

![](/files/-LoJIhdKCbc0plLc1IVp)![](/files/-LoJIhdMCvDFuf0dZuut)![](/files/-LoJIhdOhXvpB3inFbWt)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/91-decode-ways.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.