Decode Ways II

Hard
1499.

Decode Ways II

Decode Ways II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Meta interviews.

A message written in capital letters is encoded by replacing every letter with its position in the alphabet: A becomes "1", B becomes "2", …, Z becomes "26". Decoding splits the digit string into groups that each name one letter — a group is either a single digit 1–9 or two digits forming a number from 10 to 26. A group can never start with 0, so "06" is not a letter.

The encoded string s may also contain the wildcard *, which stands for any single digit from 1 to 9 (never 0). Every choice of digits for the wildcards combined with every valid grouping counts as a separate decoding.

Return the number of ways to decode s. The count grows quickly, so return it modulo 10^9 + 7.

Example 1

Input
s = "*"
Output
9
Explanation
The wildcard is one of `1`–`9`, and each of those is one letter (`A`–`I`).

Example 2

Input
s = "1*"
Output
18
Explanation
`"11"`…`"19"` are 9 strings, and each decodes two ways: as two single digits or as one two-digit group.

Example 3

Input
s = "*0"
Output
2
Explanation
A lone `0` is never a letter, so the pair must be one group: `"10"` (J) or `"20"` (T).

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is a digit or '*'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Decode Ways II — Solution in Python, Java & C++

Decode Ways II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Decode Ways II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Meta interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A message written in capital letters is encoded by replacing every letter with its position in the alphabet: A becomes "1", B becomes "2", …, Z becomes "26". Decoding splits the digit string into groups that each name one letter — a group is either a single digit 1–9 or two digits forming a number from 10 to 26. A group can never start with 0, so "06" is not a letter.

The encoded string s may also contain the wildcard *, which stands for any single digit from 1 to 9 (never 0). Every choice of digits for the wildcards combined with every valid grouping counts as a separate decoding.

Return the number of ways to decode s. The count grows quickly, so return it modulo 10^9 + 7.

Example 1

Input: s = "*"
Output: 9
Explanation: The wildcard is one of `1`–`9`, and each of those is one letter (`A`–`I`).

Example 2

Input: s = "1*"
Output: 18
Explanation: `"11"`…`"19"` are 9 strings, and each decodes two ways: as two single digits or as one two-digit group.

Example 3

Input: s = "*0"
Output: 2
Explanation: A lone `0` is never a letter, so the pair must be one group: `"10"` (J) or `"20"` (T).

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is a digit or '*'

Hints for Decode Ways II

  1. Hint 1

    Let f(i) be the number of decodings of the first i characters. The last group is either the last character alone or the last two characters together.

  2. Hint 2

    Count how many letters a single character can be (* → 9, 0 → 0, any other digit → 1) and how many valid two-digit codes a pair of characters can be.

  3. Hint 3

    For a pair: ** → 15 (11–19 and 21–26), *d → 2 when d ≤ 6 and 1 otherwise, 1* → 9, 2* → 6, two digits → 1 if they form 10–26. Then f(i) = single · f(i-1) + pair · f(i-2), reduced modulo 10^9 + 7.

How to solve Decode Ways II

It is the classic Decode Ways recurrence — the last group is one character or two — except that each option now comes with a multiplicity: the number of digit choices that make that group a valid letter. Multiply each branch by its multiplicity and the wildcards are handled without ever expanding them.

Approach

  1. Define single(c): 9 for *, 0 for 0, 1 for any other digit.
  2. Define pair(a, b): for a = * it is 15 if b = *, else 2 when b ≤ 6 (1b and 2b) and 1 otherwise (only 1b); for a = 1 it is 9 if b = * else 1; for a = 2 it is 6 if b = * else 1 when b ≤ 6 and 0 otherwise; any other a gives 0.
  3. Keep the last two values: f(0) = 1, f(1) = single(s[0]).
  4. For every next index i: f(i+1) = (single(s[i]) · f(i) + pair(s[i-1], s[i]) · f(i-1)) mod (10^9 + 7).
  5. Return the final value.

Why it works

Every decoding ends with exactly one of the two group shapes, and the choices for the last group are independent of how the prefix before it was decoded, so the count for a prefix is the sum over both shapes of (ways to fill the last group) × (ways to decode what precedes it). The multiplicities are just the number of two-digit numbers in 10–26 (or digits in 1–9) that match the pattern, which is what the small table enumerates.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • * never stands for 0, so ** is 15, not 17 — 10 and 20 are not reachable.
  • * followed by a digit d ≤ 6 (including 0) has two readings, 1d and 2d; with d ≥ 7 only 1d works.
  • The products reach about 2.4 · 10^10 before the modulus, so use 64-bit integers in Java, C, C#, Kotlin and Rust.

Reference solution

Python

def numDecodings(s: str) -> int:
    MOD = 10 ** 9 + 7

    def single(c):
        if c == '*':
            return 9
        return 0 if c == '0' else 1

    def pair(a, b):
        if a == '*':
            if b == '*':
                return 15
            return 2 if b <= '6' else 1
        if a == '1':
            return 9 if b == '*' else 1
        if a == '2':
            if b == '*':
                return 6
            return 1 if b <= '6' else 0
        return 0

    prev2, prev1 = 1, single(s[0])
    for i in range(1, len(s)):
        prev2, prev1 = prev1, (single(s[i]) * prev1 + pair(s[i - 1], s[i]) * prev2) % MOD
    return prev1

Java

static long decodeSingle(char c) {
    if (c == '*') return 9;
    return c == '0' ? 0 : 1;
}

static long decodePair(char a, char b) {
    if (a == '*') {
        if (b == '*') return 15;
        return b <= '6' ? 2 : 1;
    }
    if (a == '1') return b == '*' ? 9 : 1;
    if (a == '2') {
        if (b == '*') return 6;
        return b <= '6' ? 1 : 0;
    }
    return 0;
}

public static int numDecodings(String s) {
    final long MOD = 1000000007L;
    long prev2 = 1, prev1 = decodeSingle(s.charAt(0));
    for (int i = 1; i < s.length(); i++) {
        long cur = (decodeSingle(s.charAt(i)) * prev1 + decodePair(s.charAt(i - 1), s.charAt(i)) * prev2) % MOD;
        prev2 = prev1;
        prev1 = cur;
    }
    return (int) prev1;
}

C++

long long decodeSingle(char c) {
    if (c == '*') return 9;
    return c == '0' ? 0 : 1;
}

long long decodePair(char a, char b) {
    if (a == '*') {
        if (b == '*') return 15;
        return b <= '6' ? 2 : 1;
    }
    if (a == '1') return b == '*' ? 9 : 1;
    if (a == '2') {
        if (b == '*') return 6;
        return b <= '6' ? 1 : 0;
    }
    return 0;
}

int numDecodings(string s) {
    const long long MOD = 1000000007LL;
    long long prev2 = 1, prev1 = decodeSingle(s[0]);
    for (size_t i = 1; i < s.size(); i++) {
        long long cur = (decodeSingle(s[i]) * prev1 + decodePair(s[i - 1], s[i]) * prev2) % MOD;
        prev2 = prev1;
        prev1 = cur;
    }
    return (int)prev1;
}

JavaScript

var numDecodings = function(s) {
    var MOD = 1000000007;
    var single = function(c) {
        if (c === '*') return 9;
        return c === '0' ? 0 : 1;
    };
    var pair = function(a, b) {
        if (a === '*') {
            if (b === '*') return 15;
            return b <= '6' ? 2 : 1;
        }
        if (a === '1') return b === '*' ? 9 : 1;
        if (a === '2') {
            if (b === '*') return 6;
            return b <= '6' ? 1 : 0;
        }
        return 0;
    };
    var prev2 = 1, prev1 = single(s[0]);
    for (var i = 1; i < s.length; i++) {
        var cur = (single(s[i]) * prev1 + pair(s[i - 1], s[i]) * prev2) % MOD;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming