Skip to main content

639. Decode Ways II

hard

Count decodings of a string of digits where the wildcard '*' stands for any of 1-9. Decode Ways with branching multipliers — every '*' splits the count and you must take everything mod 10^9 + 7.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into "AAJF" with the grouping (1 1 10 6), or "KJF" with the grouping (11 10 6). In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent. Given a string s consisting of digits and '*' characters, return the number of ways to decode it. Since the answer may be very large, return it modulo 10^9 + 7.

Constraints

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

Examples

Example 1

Input
s = "*"
Output
9

Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9". Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively. Hence, there are a total of 9 ways to decode "*".

Example 2

Input
s = "1*"
Output
18

Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K"). Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3

Input
s = "2*"
Output
15

Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29". "21" - "26" have 2 ways while "27" - "29" have only one way. So 6 * 2 + 3 * 1 = 15.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i] = number of ways to decode the first i chars of s, mod 10^9 + 7.

Hint 2

Two contributions at position i: single-char contribution depends on s[i-1], two-char contribution depends on (s[i-2], s[i-1]).

Hint 3

Enumerate the cases: '*' contributes 9 single decodes; '*' '*' contributes 15 two-decodes; '1' '*' contributes 9 two-decodes; '2' '*' contributes 6 two-decodes; '*' digit splits on the digit's value.

Hint 4

Apply mod after every addition / multiplication to keep numbers bounded.

Solution approach

Reveal approach

Bottom-up DP with two rolling scalars or a 1D array of length n+1. dp[i] = number of decodings of s[0..i-1], modulo 10^9 + 7. Initialize dp[0] = 1. For each i from 1 to n: compute the single-char contribution from s[i-1] — a fixed digit yields 1 if 1..9 and 0 if '0'; a '*' yields 9. Multiply that by dp[i-1] and add to dp[i]. Then if i >= 2, compute the two-char contribution from (s[i-2], s[i-1]) by case analysis on each combination of digit/star, multiply by dp[i-2], and add. Take mod after each addition. Return dp[n]. The recurrence is just Decode Ways with extra fan-out per '*'.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta

Practice these live with InterviewChamp.AI

Drill Decode Ways II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →