# LC091 - Decode Ways

## Problem

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

**Input:** s = "12"

**Output:** 2

**Explanation:** "12" could be decoded as "AB" (1 2) or "L" (12).

**Case**

* 1 -> 1, 10-19
* 2 -> 2, 20-16
* 3-9 -> 3-9

## Solution

### Cached Recursive

Count based on how many ways the characters can be interpreted. Use cache decorator `@cache` for caching. Time complexity is $$O(n)$$, and $$O(n)$$ space complexity.

```python
def numDecodings(self, s: str) -> int:
	# cache results
	@cache
	def recurse(i):
		# reach end
		if i >= len(s)
			return 1
		# start on zero
		elif s[i] == "0":
			return 0
		# double digit handling
		if i < len(s) - 1 and int(s[i:i+2]) <= 26:
			return recurse(i+1) + recurse(i+2)
		else:
			return recurse(i+1)
	return recurse(0)
```

### Dynamic Programming

Notice that how many ways a string can be decoded is dependent on how many ways its constituent substrings can be decoded. Time and space complexity are still both $$O(n)$$.

```python
def numDecodings(self, s: str) -> int:
	pre = 0
	cur = 1

	for i in range(len(s)):
		nxt = 0
		# if cur not 0, continue
		if s[i] != "0":
			nxt = cur
		# if cur and pre <= 26
		if i > 0 and s[i-1] != "0" and (s[i-1] == "1" or s[i-1] == "2" and s[i] <= "6"):
			nxt += pre
			
		pre = cur
		cur = nxt
		
	return cur
	
```