# LeetCode 639: Decode Ways II

## Problem Restatement

We are given a string `s`.

The string contains digits and the wildcard character `*`.

The normal decoding rule is:

| Code | Letter |
|---|---|
| `"1"` | `A` |
| `"2"` | `B` |
| ... | ... |
| `"26"` | `Z` |

The wildcard `*` can represent any digit from `"1"` to `"9"`.

It cannot represent `"0"`.

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

Because the answer can be large, return it modulo:

```python
10**9 + 7
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing digits and `*` |
| Output | Number of valid decodings modulo `10^9 + 7` |
| Valid single code | `"1"` to `"9"` |
| Valid two-digit code | `"10"` to `"26"` |
| Wildcard rule | `*` means any digit from `"1"` to `"9"` |

Example function shape:

```python
def numDecodings(s: str) -> int:
    ...
```

## Examples

Example 1:

```python
s = "*"
```

`*` can be any digit from `1` to `9`.

So there are:

```python
9
```

ways.

Output:

```python
9
```

Example 2:

```python
s = "1*"
```

For single-character decoding:

```text
"1" + "*"
```

The `*` has `9` choices, so this gives `9` ways.

For two-character decoding:

```text
"1*"
```

The `*` can be `1` to `9`, giving:

```text
11, 12, 13, 14, 15, 16, 17, 18, 19
```

That gives another `9` ways.

Total:

```python
18
```

Example 3:

```python
s = "2*"
```

Single-character decoding gives `9` ways.

Two-character decoding can be:

```text
21, 22, 23, 24, 25, 26
```

That gives `6` ways.

Total:

```python
15
```

## First Thought: Expand Every `*`

A direct approach is to replace every `*` with digits from `1` to `9`.

Then for every expanded string, run the normal Decode Ways algorithm.

This is too slow.

If the string has `m` wildcard characters, there are:

```python
9**m
```

expanded strings.

We need to count choices without generating them.

## Key Insight

This is the same dynamic programming structure as Decode Ways.

At each position, the current character can contribute in two ways:

| Choice | Meaning |
|---|---|
| Single character | Decode `s[i]` alone |
| Two characters | Decode `s[i - 1:i + 1]` together |

The difference is that `*` can represent many possible digits.

So instead of asking whether a character or pair is valid, we ask:

```text
How many valid decodings can this character or pair represent?
```

Define two helper functions:

```python
ways_one(ch)
```

returns the number of valid single-character decodings.

```python
ways_two(a, b)
```

returns the number of valid two-character decodings.

Then the recurrence is:

```python
dp[i] = ways_one(s[i - 1]) * dp[i - 1] + ways_two(s[i - 2], s[i - 1]) * dp[i - 2]
```

Here, `dp[i]` means the number of ways to decode the first `i` characters.

## Counting Single Characters

For one character:

| Character | Ways | Reason |
|---|---:|---|
| `"0"` | `0` | Zero cannot be decoded alone |
| `"1"` to `"9"` | `1` | Each maps to one letter |
| `"*"` | `9` | It can be `1` through `9` |

So:

```python
ways_one("*") = 9
ways_one("0") = 0
ways_one("7") = 1
```

## Counting Two Characters

For two characters, we need values from `10` to `26`.

| Pair | Ways | Valid meanings |
|---|---:|---|
| `"**"` | `15` | `11` to `19`, and `21` to `26` |
| `"1*"` | `9` | `11` to `19` |
| `"2*"` | `6` | `21` to `26` |
| `"3*"` to `"9*"` | `0` | No valid two-digit code |
| `"*0"` to `"*6"` | `2` | `10` to `16`, or `20` to `26` |
| `"*7"` to `"*9"` | `1` | `17` to `19` |
| digit + digit | `1` if between `10` and `26`, else `0` |

The case `"**"` has `15` ways because:

```text
11, 12, 13, 14, 15, 16, 17, 18, 19
21, 22, 23, 24, 25, 26
```

That is `9 + 6 = 15`.

## Algorithm

1. Let `dp0` represent `dp[i - 2]`.
2. Let `dp1` represent `dp[i - 1]`.
3. Initialize:
   1. `dp0 = 1`, for the empty prefix.
   2. `dp1 = ways_one(s[0])`.
4. For each index `i` from `1` to `len(s) - 1`:
   1. Compute the single-character contribution.
   2. Compute the two-character contribution.
   3. Add both under modulo.
   4. Shift the rolling DP variables.
5. Return `dp1`.

## Implementation

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        MOD = 10**9 + 7

        def ways_one(ch: str) -> int:
            if ch == "*":
                return 9
            if ch == "0":
                return 0
            return 1

        def ways_two(a: str, b: str) -> int:
            if a == "*" and b == "*":
                return 15

            if a == "*":
                if "0" <= b <= "6":
                    return 2
                return 1

            if b == "*":
                if a == "1":
                    return 9
                if a == "2":
                    return 6
                return 0

            value = int(a + b)
            if 10 <= value <= 26:
                return 1

            return 0

        prev2 = 1
        prev1 = ways_one(s[0])

        for i in range(1, len(s)):
            current = ways_one(s[i]) * prev1
            current += ways_two(s[i - 1], s[i]) * prev2
            current %= MOD

            prev2 = prev1
            prev1 = current

        return prev1
```

## Code Explanation

The helper:

```python
ways_one(ch)
```

counts how many valid one-character decodings `ch` can produce.

The helper:

```python
ways_two(a, b)
```

counts how many valid two-character decodings the pair `(a, b)` can produce.

The DP starts with:

```python
prev2 = 1
prev1 = ways_one(s[0])
```

`prev2 = 1` means the empty prefix has one way.

`prev1` is the number of ways to decode the first character.

For each next character, the answer is built from two sources.

Single-character contribution:

```python
ways_one(s[i]) * prev1
```

This means we decode `s[i]` alone, after decoding the prefix before it.

Two-character contribution:

```python
ways_two(s[i - 1], s[i]) * prev2
```

This means we decode the last two characters together, after decoding the prefix before those two characters.

Then we shift:

```python
prev2 = prev1
prev1 = current
```

so the next loop has the correct previous states.

## Correctness

Let `dp[i]` be the number of ways to decode the first `i` characters of `s`.

For the last character of the first `i` characters, every valid decoding falls into exactly one of two cases.

First, the last character is decoded alone. The number of possibilities for this last character is `ways_one(s[i - 1])`. The prefix before it has `dp[i - 1]` valid decodings. So this contributes:

```python
ways_one(s[i - 1]) * dp[i - 1]
```

Second, the last two characters are decoded together. The number of valid two-character meanings is `ways_two(s[i - 2], s[i - 1])`. The prefix before them has `dp[i - 2]` valid decodings. So this contributes:

```python
ways_two(s[i - 2], s[i - 1]) * dp[i - 2]
```

These two cases are disjoint because the final decoding unit has length either one or two. They also cover all valid decodings because every decoding ends with either one character or two characters.

Therefore, the recurrence counts exactly all valid decodings.

The rolling variables `prev2` and `prev1` store `dp[i - 2]` and `dp[i - 1]`, so the implementation computes the same recurrence. Thus the returned value is correct.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(1)` | Only rolling DP variables are stored |

## Alternative Solution: DP Array

A full DP array can make the recurrence easier to inspect.

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        MOD = 10**9 + 7

        def ways_one(ch: str) -> int:
            if ch == "*":
                return 9
            if ch == "0":
                return 0
            return 1

        def ways_two(a: str, b: str) -> int:
            if a == "*" and b == "*":
                return 15
            if a == "*":
                return 2 if "0" <= b <= "6" else 1
            if b == "*":
                if a == "1":
                    return 9
                if a == "2":
                    return 6
                return 0

            return 1 if 10 <= int(a + b) <= 26 else 0

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

        dp[0] = 1
        dp[1] = ways_one(s[0])

        for i in range(2, n + 1):
            dp[i] += ways_one(s[i - 1]) * dp[i - 1]
            dp[i] += ways_two(s[i - 2], s[i - 1]) * dp[i - 2]
            dp[i] %= MOD

        return dp[n]
```

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

## Testing

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

    assert s.numDecodings("*") == 9
    assert s.numDecodings("1*") == 18
    assert s.numDecodings("2*") == 15
    assert s.numDecodings("**") == 96
    assert s.numDecodings("0") == 0
    assert s.numDecodings("10") == 1
    assert s.numDecodings("*0") == 2
    assert s.numDecodings("30") == 0
    assert s.numDecodings("**********") == 483456820

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"*"` | Single wildcard has 9 choices |
| `"1*"` | Single and pair contributions both matter |
| `"2*"` | Pair contribution has 6 choices |
| `"**"` | Checks the `15` two-character wildcard case |
| `"0"` | Zero cannot stand alone |
| `"10"` | Zero can appear inside a valid pair |
| `"*0"` | Only `10` and `20` are valid |
| `"30"` | Invalid two-character code |
| Many wildcards | Checks modulo handling |