medium

Decode Ways

Count how many ways a string of digits can be decoded into letters.

1. Define the problem

Decode Ways

Letters were turned into numbers with A = 1, B = 2, and so on up to Z = 26, then all the digits were run together. Given that string of digits, count how many different messages it could have been. For example "12" could be "AB" (1 then 2) or "L" (12), so the answer is 2. Read the digits left to right. At each digit you either take it on its own or pair it with the digit before it, and a pair only counts when it lands between 10 and 26 . A zero can never stand alone, so the count for a position is the count from one step back plus the count from two steps back, keeping only the options that are legal.

Constraints

  • 1 ≤ s.length ≤ 100
  • s contains only digits
  • s may contain leading zeros, in which case the answer is 0

Example

Inputs = "2263"
Output3

Explanation "2263" reads as "BBFC" (2 2 6 3), "VFC" (22 6 3) or "BZC" (2 26 3), so there are 3 ways.

2. Know the words first

In plain terms

Decode
Turn the digits back into letters. The same digits can often be read more than one way, which is why they need counting.
Valid pair
Two digits read as a single letter. It has to be 10 to 26: "07" is not valid because no letter is number 7 written with a leading zero, and "27" is past Z.
Running count
The number of ways to decode everything up to a point. Each new count is built from the two counts before it, so only those two need remembering.
3. Visualize the solution

Count the ways to read each prefix of the digits

Count the ways to read each prefix of the digits
Statusinit

Start with one way to decode nothing and one way to decode "2".

What happens in this step

s = "2263"
position 0 = 1, position 1 = 1

The first digit is 2, not zero, so "2" reads as B and nothing else. The later positions have not been worked out yet.
Step 1 of 5

Steps to visualize

  1. The row is the 5 cut positions of "2263", from 0 (before any digit) to 4 (after the last).
  2. Each cell holds the number of ways to decode the digits up to that position.
  3. Position 0 is 1: there is exactly one way to decode nothing.
  4. Position 1 is 1 as long as the first digit is not zero.
  5. A digit that is not zero can stand alone, adding the count from one position back.
  6. A pair of digits between 10 and 26 adds the count from two positions back.
  7. The last cell is the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count the ways to read each prefix of the digits
Statusinit

Start with one way to decode nothing and one way to decode "2".

What happens in this step

s = "2263"
position 0 = 1, position 1 = 1

The first digit is 2, not zero, so "2" reads as B and nothing else. The later positions have not been worked out yet.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function numDecodings(s) {
  if (s.length === 0 || s[0] === '0') {
    return 0;
  }

  let twoBack = 1;
  let oneBack = 1;

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

    if (s[i] !== '0') {
      current += oneBack;
    }

    const pair = Number(s.slice(i - 1, i + 1));
    if (pair >= 10 && pair <= 26) {
      current += twoBack;
    }

    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
s = "2263"3example from the description
s = "12"2smallest string with more than one reading
s = "226"3overlapping pairs 22 and 26
s = "06"0a string that cannot be decoded at all
s = "10"1a zero that only works as part of a pair
s = "1111"5a longer string where the counts grow

Keep reading