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:

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:

10**9 + 7

Input and Output

Example function shape:

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

Examples

Example 1:

s = "*"

* can be any digit from 1 to 9.

So there are:

9

ways.

Output:

9

Example 2:

s = "1*"

For single-character decoding:

"1" + "*"

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

For two-character decoding:

"1*"

The * can be 1 to 9, giving:

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

That gives another 9 ways.

Total:

18

Example 3:

s = "2*"

Single-character decoding gives 9 ways.

Two-character decoding can be:

21, 22, 23, 24, 25, 26

That gives 6 ways.

Total:

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:

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:

The difference is that * can represent many possible digits.

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

How many valid decodings can this character or pair represent?

Define two helper functions:

ways_one(ch)

returns the number of valid single-character decodings.

ways_two(a, b)

returns the number of valid two-character decodings.

Then the recurrence is:

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:

So:

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

Counting Two Characters

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

The case "**" has 15 ways because:

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

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:

ways_one(ch)

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

The helper:

ways_two(a, b)

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

The DP starts with:

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:

ways_one(s[i]) * prev1

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

Two-character contribution:

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:

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:

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:

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).

Alternative Solution: DP Array

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

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]

Testing

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: