# 91. Decode Ways

#### Medium

***

A message containing letters from `A-Z` can be **encoded** into numbers using the following mapping:

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

To **decode** an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into:

* `"AAJF"` with the grouping `(1 1 10 6)`
* `"KJF"` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`.

Given a string `s` containing only digits, return *the **number** of ways to **decode** it*.

The test cases are generated so that the answer fits in a **32-bit** integer.

 

**Example 1:**

```
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
```

**Example 2:**

```
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```

**Example 3:**

```
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
```

 

**Constraints:**

* `1 <= s.length <= 100`
* `s` contains only digits and may contain leading zero(s).

### Solution

First, I build a tree of possible decodings I can do from a random string.

* The number of leaves in the tree essentially is the number of ways the string can be decoded.
* We are going to build our tree with DFS from our original string, trying to decode either as:
  * A single digit (and call dfs again with remaining string)
  * Both single digit and double digit

<img src="https://1865766684-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLgwjo4Xadqnv6PXZEA0Z%2Fuploads%2FvdAdYwRskVQ1MXsBFvUi%2Fimage.png?alt=media&#x26;token=5b4165e0-6586-497d-b136-b914200c19f5" alt="" data-size="original">![](https://1865766684-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLgwjo4Xadqnv6PXZEA0Z%2Fuploads%2FaoRQupJ5zBsbAExMgpaR%2Fimage.png?alt=media\&token=b5bca046-fda4-4da1-abbf-95565834628b)

We can see redundant sub-trees so this calls up for dynamic programming.

**My solution** :&#x20;

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        # Similar to staircase problem
        arr = [0]*(len(s)+1)
        arr[0] = 1
        arr[1] = 0 if s[0] == '0' else 1
        for index in range(2, len(s)+1):
            # one step
            if 0 < int(s[index-1:index]) <=9:
                arr[index] += arr[index-1]
            if 10 <= int(s[index-2:index]) <= 26:
                arr[index] += arr[index-2]
        return arr[len(s)]
            
```

**Other Solution** :thumbsup:

```python
class Solution:
    def numDecodings(self, s:str) -> int:
        if len(s) == 0 or s is None:
            return 0

        @lru_cache(maxsize=None)
        def dfs(string):
            if len(string)>0:
                if string[0] == '0':
                    return 0
            if string == "" or len(string) == 1:
                return 1
            if int(string[0:2]) <= 26:
                first = dfs(string[1:])
                second = dfs(string[2:])
                return first+second
            else:
                return dfs(string[1:])

        result_sum = dfs(s)

        return result_sum
```