# LeetCode 91: Decode Ways

## Problem Restatement

We are given a string `s` containing only digits.

The digits encode letters using this mapping:

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

We need to count how many different ways the string can be decoded.

A digit group is valid only if it maps to a number from `1` to `26`.

So:

```python
"12"
```

can be decoded as:

```python
"1" "2" -> "AB"
"12"    -> "L"
```

The answer is `2`.

The official constraints are `1 <= s.length <= 100`, `s` contains only digits, and it may contain leading zeroes. The answer fits in a 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A digit string `s` |
| Output | Number of valid decodings |
| Valid single digit | `"1"` to `"9"` |
| Valid two digits | `"10"` to `"26"` |
| Invalid digit group | `"0"` alone, or a number with leading zero like `"06"` |

Function shape:

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        ...
```

## Examples

Example 1:

```python
s = "12"
```

Valid decodings:

```python
"1" "2" -> "AB"
"12"    -> "L"
```

Answer:

```python
2
```

Example 2:

```python
s = "226"
```

Valid decodings:

```python
"2" "2" "6" -> "BBF"
"22" "6"    -> "VF"
"2" "26"    -> "BZ"
```

Answer:

```python
3
```

Example 3:

```python
s = "06"
```

This is invalid.

`"0"` does not map to any letter.

`"06"` is also invalid because it has a leading zero.

Answer:

```python
0
```

## First Thought: Recursion

At each index, we have at most two choices.

We can take one digit if it is between `"1"` and `"9"`.

We can take two digits if they form a number between `"10"` and `"26"`.

So from index `i`, the answer is:

```python
ways(i) = ways(i + 1) + ways(i + 2)
```

but only when those one-digit and two-digit choices are valid.

A direct recursive solution works logically, but it repeats the same suffix many times.

For example, in `"226"`, both paths may ask how many ways exist for the suffix starting at the last character.

This repeated work suggests dynamic programming.

## Key Insight

Let:

```python
dp[i]
```

mean:

```python
the number of ways to decode s[:i]
```

So `dp[0]` means the empty prefix.

We set:

```python
dp[0] = 1
```

This does not mean the empty string is an answer. It means there is one neutral way to decode nothing, so later valid choices can build from it.

For each position `i`, we consider the last one digit and the last two digits.

For prefix `s[:i]`, the last one digit is:

```python
s[i - 1]
```

The last two digits are:

```python
s[i - 2:i]
```

## Transition

If the last one digit is valid, then it can stand alone.

That means every decoding of `s[:i - 1]` can be extended by this one digit.

```python
if s[i - 1] != "0":
    dp[i] += dp[i - 1]
```

If the last two digits form a valid number from `10` to `26`, then every decoding of `s[:i - 2]` can be extended by this two-digit letter.

```python
if 10 <= int(s[i - 2:i]) <= 26:
    dp[i] += dp[i - 2]
```

The valid two-digit check starts at `10`, so strings like `"06"` are rejected.

## Algorithm

Create an array:

```python
dp = [0] * (len(s) + 1)
```

Set:

```python
dp[0] = 1
```

Then loop:

```python
i = 1, 2, ..., len(s)
```

At each `i`:

1. If `s[i - 1]` is not `"0"`, add `dp[i - 1]`.
2. If `i >= 2` and `s[i - 2:i]` is between `"10"` and `"26"`, add `dp[i - 2]`.
3. Return `dp[len(s)]`.

## Walkthrough

Use:

```python
s = "226"
```

Create:

```python
dp = [1, 0, 0, 0]
```

At `i = 1`, prefix is:

```python
"2"
```

Single digit `"2"` is valid.

```python
dp[1] += dp[0]
```

Now:

```python
dp = [1, 1, 0, 0]
```

At `i = 2`, prefix is:

```python
"22"
```

Single digit `"2"` is valid, so add `dp[1]`.

Two digits `"22"` are valid, so add `dp[0]`.

```python
dp[2] = 2
```

Now:

```python
dp = [1, 1, 2, 0]
```

At `i = 3`, prefix is:

```python
"226"
```

Single digit `"6"` is valid, so add `dp[2]`.

Two digits `"26"` are valid, so add `dp[1]`.

```python
dp[3] = 3
```

Final answer:

```python
3
```

## Handling Zero

Zero is the main edge case.

A single `"0"` is invalid.

```python
"0" -> 0 ways
```

But `"10"` and `"20"` are valid:

```python
"10" -> "J"
"20" -> "T"
```

Other combinations ending in zero may be invalid:

```python
"30" -> invalid
"00" -> invalid
"06" -> invalid
```

The DP rules handle all of these.

For `"10"`:

```python
"0" cannot stand alone
"10" is valid
```

so the answer comes from `dp[i - 2]`.

For `"30"`:

```python
"0" cannot stand alone
"30" is not between 10 and 26
```

so the answer becomes `0`.

## Correctness

The algorithm counts decodings by the final digit group of each valid decoding.

For a prefix `s[:i]`, any valid decoding must end in either a one-digit group or a two-digit group, because the mapping only covers numbers from `1` to `26`.

If the decoding ends with one digit, that last digit must be from `"1"` to `"9"`. Removing it leaves a valid decoding of `s[:i - 1]`. The algorithm adds exactly `dp[i - 1]` for this case.

If the decoding ends with two digits, those digits must form a number from `10` to `26`. Removing them leaves a valid decoding of `s[:i - 2]`. The algorithm adds exactly `dp[i - 2]` for this case.

These two cases are disjoint because a decoding cannot end with both a one-digit group and a two-digit group at the same time.

The algorithm considers both possible final group sizes and only accepts valid groups. Therefore, `dp[i]` equals the number of valid decodings of `s[:i]`.

By induction over `i`, the final value `dp[len(s)]` is the number of valid decodings of the whole string.

## Complexity

Let:

```python
n = len(s)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each position once |
| Space | `O(n)` | The DP array has `n + 1` entries |

## Implementation

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            if s[i - 1] != "0":
                dp[i] += dp[i - 1]

            if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]
```

## Code Explanation

Create the DP array:

```python
dp = [0] * (n + 1)
```

Set the base case:

```python
dp[0] = 1
```

For each prefix length `i`:

```python
for i in range(1, n + 1):
```

Check whether the final one digit can be decoded:

```python
if s[i - 1] != "0":
    dp[i] += dp[i - 1]
```

Check whether the final two digits can be decoded:

```python
if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
    dp[i] += dp[i - 2]
```

Return the number of ways for the full string:

```python
return dp[n]
```

## Space-Optimized Implementation

Since `dp[i]` only depends on `dp[i - 1]` and `dp[i - 2]`, we can keep two variables.

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        prev2 = 1
        prev1 = 0

        for i in range(1, len(s) + 1):
            cur = 0

            if s[i - 1] != "0":
                cur += prev1 if i > 1 else prev2

            if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
                cur += prev2

            prev2, prev1 = prev1, cur

        return prev1
```

A cleaner version initializes `prev1` as the answer for the first character:

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        prev2 = 1
        prev1 = 0 if s[0] == "0" else 1

        for i in range(2, len(s) + 1):
            cur = 0

            if s[i - 1] != "0":
                cur += prev1

            if 10 <= int(s[i - 2:i]) <= 26:
                cur += prev2

            prev2, prev1 = prev1, cur

        return prev1
```

Space complexity becomes:

| Metric | Value |
|---|---|
| Time | `O(n)` |
| Space | `O(1)` |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numDecodings("12") == 2
    assert s.numDecodings("226") == 3
    assert s.numDecodings("06") == 0

    assert s.numDecodings("0") == 0
    assert s.numDecodings("10") == 1
    assert s.numDecodings("20") == 1
    assert s.numDecodings("30") == 0
    assert s.numDecodings("100") == 0
    assert s.numDecodings("101") == 1
    assert s.numDecodings("11106") == 2
    assert s.numDecodings("27") == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"12"` | Main small example |
| `"226"` | Multiple valid groupings |
| `"06"` | Leading zero invalid |
| `"0"` | Single zero invalid |
| `"10"` | Zero valid only as part of `10` |
| `"20"` | Zero valid only as part of `20` |
| `"30"` | Invalid zero pair |
| `"100"` | Final zero cannot stand alone |
| `"101"` | Valid split `10, 1` |
| `"11106"` | Mixed valid and invalid branches |
| `"27"` | Cannot decode `27` as one letter |