Marauder Bot

Problem

A string of digits encodes a message where the letters A through Z correspond to the numbers 1 through 26. Given such a digit string, count how many distinct ways it could have been decoded back into letters.

Example. For "226", there are 3 valid decodings: 2, 2, 6 (B, B, F), 22, 6 (V, F), and 2, 26 (B, Z).

Key idea

Trying every way to split the digits into groups recursively revisits the same remaining substrings again and again, so a naive recursive count grows exponentially. The fix is to build the count for each prefix of the string from smaller, already-solved prefixes.

For the prefix ending at a given position, there are at most two ways the final letter could have ended: as a single digit, or as the last two digits grouped together. If the last digit alone is a valid code (nonzero), every way of decoding everything before it still works, contributing that smaller prefix's count. If the last two digits together form a valid code (10 through 26), every way of decoding everything before those two digits also works, contributing that count too. Summing the valid contributions gives the count for the current prefix, and building up from the empty prefix means each new position only needs the two counts immediately before it.

Solution

function numDecodings(s: string): number {
  if (s.length === 0 || s[0] === '0') {
    return 0;
  }

  let prevCount = 1; // ways to decode the empty prefix
  let currentCount = 1; // ways to decode the first character

  for (let i = 1; i < s.length; i++) {
    let ways = 0;

    const oneDigit = Number(s[i]);
    if (oneDigit >= 1) {
      ways += currentCount; // this digit alone is a valid letter (nonzero)
    }

    const twoDigit = Number(s.slice(i - 1, i + 1));
    if (twoDigit >= 10 && twoDigit <= 26) {
      ways += prevCount; // this digit paired with the previous one is valid (10-26)
    }

    prevCount = currentCount;
    currentCount = ways;
  }

  return currentCount;
}

Complexity

Time: O(n). One pass over the digits, doing constant work at each position.
Space: O(1). Only the previous two prefix counts are needed at any time.

Watch out for

A 0 digit can never represent a letter alone, so it is only valid as the second digit of a 10 or 20 grouping; any other placement kills that path.
Two-digit groupings are only valid from 10 through 26; a leading digit of 3 or higher cannot be grouped.
A string that starts with 0 has no valid decodings at all.

Pattern

This is the same "sum contributions from one or two prior states" linear DP shape as Climbing Stairs, with the twist that each contribution is gated by a domain-specific validity check instead of always being available.

Decode Ways