Decode Ways

The problem

A message of capital letters was turned into digits: A became 1, B became 2, and so on up to Z, which became 26. The codes were written one after another with nothing between them. Given the digit string s, return how many different messages it could stand for. Each code must be a whole number from 1 to 26 with no 0 in front, so a 0 is never a letter alone and 06 is not F. Return 0 if s cannot be read at all.

What to write

function solve(s: string): number

Input
s = "12"

Output
2

Input
s = "226"

Output
3

Constraints

s is nonempty and the answer fits a signed 32-bit integer.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The answer fits a signed 32-bit integer, so it can be as large as about two billion. Listing the possible messages one at a time could take that many steps, so you have to count them without building them. Also note which digit can never be a letter by itself.

2. Hint 2: Ask a smaller question

   Call each way of reading the digits a decoding. Write out all the decodings of 226 and sort them by their last letter. What do the decodings in one group look like once you cover up that last letter?

3. Hint 3: Name the pattern

   Every decoding ends with a letter made of one digit or of two. Take that letter away and a shorter string is left, with a count of its own. Building each count from the counts of shorter strings, each worked out once, is one-dimensional dynamic programming. The signal: you are asked how many ways, not which ways. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Keep two counts while you walk through the digits. When you reach a digit, one count is the number of ways to decode everything before that digit. The other is the number of ways to decode everything before the digit in front of it. Nothing read yet counts as one way.

5. Hint 5: Sketch the pseudocode

   older = 1. newer = 0 if the first digit is 0, otherwise 1. For each later digit: next = newer if the digit is not 0, otherwise 0. If the digit before and this digit together read as 10 to 26, add older to next. Then older = newer and newer = next. Return newer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

A valid final letter uses either one nonzero digit or a pair between 10 and 26. Add the corresponding prior counts.

The slow way

Call each way of reading the digits a decoding. The slow way builds them all: at each place it takes one digit or two, and counts the cuts in which every piece is a valid code. It is correct, but a string of thirty 1s has 1,346,269 decodings, and counting them this way takes 3,524,577 calls.

The insight

Sort the decodings by their last letter. Those ending with a one-digit letter are the decodings of the string without its last digit, each with that letter added. Those ending with a two-digit letter are the decodings of the string without its last two digits. So two earlier counts add up to the next one.

Step by step

1. Count one way to read nothing, and the ways to read the first digit. A pair at the very start has nothing before it, and it is still one decoding, so nothing read counts as one way. The first digit is a letter unless it is 0.
2. A digit other than 0 is a letter alone: keep the count before it. Each decoding of the digits before it can be followed by this one-digit letter. A 0 is no letter, so in that case none of them can.
3. A pair from 10 to 26 is a letter too: add the count before the pair. Each decoding of the digits before the pair can be followed by this two-digit letter. Below 10 the pair would start with 0, and above 26 there is no letter.
4. Slide both counts one digit to the right. The next digit needs the count for everything before it, which is the new count, and the count for everything before this digit, which was the newer one until now.
5. Return the count for the whole string. After the last digit, the newer count covers every digit of the string. For a single digit the loop never runs, and the starting count is returned.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Count one way to read nothing, and the ways to read the first digit
  let two = 1,
    one = s[0] === "0" ? 0 : 1;
  // At each digit, "one" is the count one digit back, "two" two digits back.
  for (let i = 1; i < s.length; i++) {
    // 2. A digit other than 0 is a letter alone: keep the count before it
    let cur = s[i] === "0" ? 0 : one;
    // 3. A pair from 10 to 26 is a letter too: add the count before the pair
    const pair = Number(s.slice(i - 1, i + 1));
    if (pair >= 10 && pair <= 26) cur += two;
    // 4. Slide both counts one digit to the right
    two = one;
    one = cur;
  }
  // 5. Return the count for the whole string
  return one;
}

function solve(s: string): number {
  // 1. Count one way to read nothing, and the ways to read the first digit
  let two = 1,
    one = s[0] === "0" ? 0 : 1;
  // At each digit, "one" is the count one digit back, "two" two digits back.
  for (let i = 1; i < s.length; i++) {
    // 2. A digit other than 0 is a letter alone: keep the count before it
    let cur = s[i] === "0" ? 0 : one;
    // 3. A pair from 10 to 26 is a letter too: add the count before the pair
    const pair = Number(s.slice(i - 1, i + 1));
    if (pair >= 10 && pair <= 26) cur += two;
    // 4. Slide both counts one digit to the right
    two = one;
    one = cur;
  }
  // 5. Return the count for the whole string
  return one;
}

def solve(s):
    # 1. Count one way to read nothing, and the ways to read the first digit
    two = 1
    one = 0 if s[0] == "0" else 1
    # At each digit, "one" is the count one digit back, "two" two digits back.
    for i in range(1, len(s)):
        # 2. A digit other than 0 is a letter alone: keep the count before it
        current = 0 if s[i] == "0" else one
        # 3. A pair from 10 to 26 is a letter too: add the count before the pair
        pair = int(s[i - 1 : i + 1])
        if 10 <= pair <= 26:
            current += two
        # 4. Slide both counts one digit to the right
        two, one = one, current
    # 5. Return the count for the whole string
    return one

Example 2, traced

Input
s = "226"

Output
3

Why it works

Before each digit is handled, one count is the number of ways to decode everything before that digit, and the other is the number for everything before the digit in front of it. A decoding ends with a one-digit letter or a two-digit letter, never both, so adding the two valid cases counts every decoding exactly once.

Time and space

Time O(n), extra space O(1). The loop visits each digit once and does a fixed amount of work there, so the time is O(n) for n digits. Only two counts are stored, however long the string is, so the space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Testing only that a pair is at most 26. The pair 06 passes that test, but no code starts with 0, so a pair must also be at least 10. Without that, 06 gives 1 instead of 0.
• Starting the count for nothing read at 0. Then a pair at the very start adds nothing, and 12 gives 1 instead of 2.
• Letting a 0 stand alone. For 10 that counts a second decoding, 1 then 0, and the answer becomes 2 instead of 1.

Pattern

One-dimensional dynamic programming. Builds on Climbing Stairs.

Keep going