Ways to read a digit string as letters (1 = A … 26 = Z)

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
def readings(s: str) -> int:
    if not s:
        return 1
    total = 0
    if s[0] != "0":
        total += readings(s[1:])
    if len(s) > 1 and 10 <= int(s[:2]) <= 26:
        total += readings(s[2:])
    return total

print(readings("226"), readings("106"), readings("30"))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 1 0

Right: 2-2-6, 22-6 and 2-26; only 10-6; and '30' has no reading.

The plain recursion repeats suffixes; caching by position turns it into the O(n) table.

Why not the others?
  • B 3 2 1. '0' cannot stand alone, so '1-0-6' and '3-0' fail.
  • C 2 1 0. '226' also reads as 2-26.

30-second answer

Let ways[i] count the readings of the first i digits. The last letter used either one digit (valid if it is not '0') or two digits (valid if they form 10 to 26). So ways[i] = (ways[i - 1] if one-digit is valid) + (ways[i - 2] if two-digit is valid), with ways[0] = 1. Two rolling values give O(n) time and O(1) memory.

Practise saying it · 45 s. No recording, just a timer

Explain counting digit readings.

Say your answer out loud, then check which of these points you covered:

  • One or two digits per letter
  • Zero rules
  • O(n)

Deep dive

Same shape as the stepping-stones count, with conditions on each step.

Zeros are the edge case: '10' and '20' are fine, '30' and '00' are dead ends.

A string starting with '0' has no readings.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def readings(digits: str) -> int:
    before, last = 0, 1  # readings of the prefix two back and one back
    for i, d in enumerate(digits):
        here = last if d != "0" else 0  # d read as one letter
        if i and 10 <= int(digits[i - 1:i + 1]) <= 26:
            here += before  # the pair read as one letter
        before, last = last, here
    return last

Common mistakes

  • Treating '0' as a letter.
  • Accepting two-digit codes like '07'.

Senior take & follow-ups

Walk through '226' and '106' out loud; together they cover the zero rules.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you list the readings?

    Show hint

    Backtracking over the same one-or-two-digit choices.

  2. What if '*' can stand for any digit 1 to 9?

    Show hint

    Multiply each term by how many digits fit; the recurrence keeps its shape.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.