Decode Ways II

Decode Ways II takes the classic "how many ways can I decode this string of digits into letters" problem and adds a wildcard. The * character can stand for any digit from 1 to 9, so a single string can fan out into a huge number of decodings. The trick is the same 1-D dynamic programming scan — we just weight each transition by how many digits the wildcard could be.

The slow way first

You could try to expand every * into all 9 possible digits and count decodings of each concrete string. With k wildcards that is 9^k strings — exponential and hopeless for anything but tiny inputs.

The question to ask: while standing at one character, what do I already know? I know the number of ways to decode everything before it. If I can express the ways up to position i using the ways up to i-1 and i-2, I never have to expand anything — I just multiply by counts.

The idea: weight each transition by a count

Walk the string left to right, keeping dp = ways to decode the prefix so far (and prev = the value two characters back). At each character there are two contributions:

• Single digit. Decode this character on its own. A normal digit 1-9 contributes a factor of 1; a 0 contributes 0 (cannot stand alone); a * contributes 9 because it could be any of nine digits.
• Pair. Combine the previous character with this one into a two-digit letter 10-26. Count how many concrete two-digit numbers in that range the (possibly wildcard) pair can form, and multiply the ways from before the pair by that count.

The key insight: a * never forces us to branch. We replace branching with a count — 9 for a lone *, and the size of the valid two-digit range for a pair.

Walk through it

Step through the animation on s = "1*". The pointer i scans the two cells. At the 1, the single-digit factor is 1 so dp stays 1. At the *, the single-digit factor is 9, lifting dp to 9. Then the pair 1* forms 11...19 — all 9 are valid two-letter decodings — so we add 9 more, landing on dp = 18.

Pseudocode

dp = 1            # ways for the empty prefix
prev = 1          # dp from two characters back
for each char ch at index i:
    cur = single_digit_factor(ch) * dp    # 9 if "*", 1 if 1-9, 0 if "0"
    if i > 0:
        cur += pairs(s[i-1], ch) * prev   # count of valid two-digit combos
    prev, dp = dp, cur mod (10^9 + 7)
return dp

The Python solution

def num_decodings(s):
    MOD = 10**9 + 7
    dp = 1           # ways for empty prefix
    prev = 1         # dp two chars back
    for i, ch in enumerate(s):
        cur = 0
        if ch == '*':
            cur = 9 * dp
        else:
            cur = (1 if ch != '0' else 0) * dp
        if i > 0:
            a, b = s[i - 1], ch
            cur += pairs(a, b) * prev
        prev, dp = dp, cur % MOD
    return dp

• dp is the number of ways to decode the prefix processed so far; prev is that value one step earlier (the "two chars back" we pair against).
• Lines 7-8: a lone * is nine single-digit decodings, so multiply the running dp by 9.
• Lines 9-10: a concrete digit decodes one way, unless it is 0, which cannot stand alone.
• Lines 10-13: from the second character on, add the pair contribution — pairs(a, b) returns how many two-digit numbers in 10-26 the pair a b can form (e.g. 1* -> 11..19 = 9, * paired as the second char widens the range, 2* -> 21..26 = 6), multiplied by prev.
• Line 14: shift the window forward, taking the answer mod 10^9 + 7.

Complexity

We keep only the last two dp values, so the extra space is O(1). Replacing branching with counts collapses an exponential search into a single linear scan.

When this pattern shows up

Practice