# Decode Ways
https://leetcode.com/problems/decode-ways/
## Approach 1: [[recursion|Recursive]] with Memoization
Either decode one digit, or decode 2 digits. The decisions make up a tree. Use memoization to reuse results from sub problems.
```python
@lru_cache(maxsize=None)
def recursiveWithMemo(index, s) -> int:
# If you reach the end of the string
# Return 1 for success.
if index == len(s):
return 1
# If the string starts with a zero, it can't be decoded
if s[index] == "0":
return 0
if index == len(s) - 1:
return 1
answer = self.recursiveWithMemo(index + 1, s)
if int(s[index:index + 2]) <= 26:
answer += recursiveWithMemo(index + 2, s)
return answer
def numDecodings(s: str) -> int:
return recursiveWithMemo(0, s)
```
Time and space complexity: $O(n)$
## Approach 2: Iterative/[[dp|DP]]
Similar to the idea in [[house-robber]], but goes from start to end.
```python
n = len(s)
# Array to store the subproblem results
dp = [0 for _ in range(n + 1)]
dp[0] = 1 # Base case is the key
# Ways to decode a string of size 1 is 1. Unless the string is '0'.
# '0' doesn't have a single digit decode.
dp[1] = 0 if s[0] == "0" else 1
for i in range(2, n):
# Check if successful single digit decode is possible.
if s[i - 1] != "0":
dp[i] = dp[i - 1]
# Check if successful two digit decode is possible.
two_digit = int(s[i - 2: i])
if 10 <= two_digit <= 26:
dp[i] += dp[i - 2]
return dp[-1]
```
Time and space: $O(n)$
## Approach 3: Optimized DP
```python
if s[0] == "0":
return 0
two_back = 1
one_back = 1
for i in range(1, len(s)):
if not (one_back or two_back):
# neither single digit nor double digit decoding worked before
return 0
current = 0
if s[i] != "0": # can do single digit
current = one_back
two_digit = int(s[i - 1:i + 1])
if 10 <= two_digit <= 26:
current += two_back # can also do two digits
two_back = one_back
one_back = current
return one_back # the last current
```