LeetCode 91 · 1-D DP

Decode Ways, explained with a picture

How many ways to read a secret number code.

Medium1-D DP
▶ Watch it step by step

The problem

A message of letters was encoded as numbers: A = 1, B = 2, …, Z = 26. Given the string of digits, count how many ways it could be decoded.

Input:  "2263"
Output: 3   (2 2 6 3 = BBFC, 22 6 3 = VFC, 2 26 3 = BZC)

Picture it

Picture reading a secret code from left to right. At each point the next letter can use one digit (if it’s 1–9) or two digits (if they form 10–26). So the number of readings up to position i = readings up to i − 1 (if a single digit works) + readings up to i − 2 (if a pair works). A 0 can never stand alone.

How to recognise it

  • You must count the ways to split a string into valid pieces (here, pieces of one or two digits).
  • The number of ways to read the first i characters depends only on the ways to read the first i − 1 and i − 2.
  • Validity rules are local: a piece is fine or not by itself, like 0 alone being illegal and 26 being legal but 27 not.
  • With up to 100 digits, listing every decoding is impossible (a string of one hundred 1s has about 5.7 × 10^20 of them).
  • "How many ways to cut a string into allowed pieces" is the 1-D dynamic programming (DP) pattern, as with Climbing Stairs plus a validity check.

Start with brute force

Try both choices at the front of the string: read one digit (if it is not 0), or read two digits (if they form 10 to 26), and add up the counts for the rest.

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

Each call can start two more, so for strings like "1111…" the time grows like 1.6^n, and with 100 digits the count of calls is over 10^20. Space is O(n) for the recursion and the slices.

From brute force to the idea

  1. Find the waste. Reading one digit then one digit, or two digits at once, lands on the same remaining string. The brute force counts the decodings of that rest twice.
  2. Define a table. Let ways[i] be the number of ways to decode the first i digits. ways[0] = 1: the empty prefix has one reading, the empty one.
  3. Last piece is one digit. If s[i-1] is not "0", every decoding of the first i − 1 digits extends by that digit: add ways[i - 1].
  4. Last piece is two digits. If s[i-2:i] is between 10 and 26, every decoding of the first i − 2 digits extends by it: add ways[i - 2]. Checking >= 10 rules out "06", which is not a valid code.
  5. Answer. ways[len(s)].

This is the key idea: the number of decodings of a prefix is the sum of two cases (last piece one digit, last piece two digits), each a smaller prefix already counted.

The key idea

ways[i] = (ways[i − 1] if s[i−1] ≠ 0) + (ways[i − 2] if 10 ≤ s[i−2:i] ≤ 26). O(n).

Python solution

def num_decodings(s):          # 1 = A … 26 = Z
    ways = [1] + [0] * len(s)    # ways[i]: ways to read the first i digits
    for i in range(1, len(s) + 1):
        if s[i - 1] != "0":
            ways[i] += ways[i - 1]         # read one digit
        if i > 1 and 10 <= int(s[i - 2:i]) <= 26:
            ways[i] += ways[i - 2]         # read two digits
    return ways[len(s)]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(1.6^n): every position can branch into two callsO(n): recursion depth and slices
Table (shown code)O(n): two checks and at most two additions per digitO(n): the ways list (two variables would give O(1))

Edge cases

  • A single zero ("0"): returns 0; no letter has code 0.
  • Leading zero ("06"): returns 0, since "06" is not a code and "0" cannot stand alone.
  • Zero after a one or two ("10"): returns 1 (only J); "100" returns 0 because the last zero has nothing to pair with.
  • Number too large ("27"): returns 1, only 2 and 7, because 27 is above 26.
  • Examples: "12" returns 2, "226" returns 3, "11106" returns 2.
  • Counts grow quickly: 100 ones give 573147844013817084101, which Python holds exactly. LeetCode promises that real answers fit in 32 bits.
  • Empty string: returns 1, the one empty reading. The problem always gives at least one digit.

Common mistakes

  • Forgetting the "0" check for the one-digit case, so "10" returns 2 (see the quiz).
  • Testing two digits with int(...) <= 26 but no lower bound, so "06" counts as a valid code.
  • Setting ways[0] = 0, which makes every count 0.
  • Treating "0" as decodable when it follows a number like 3: "30" has no valid reading.
Your turn: a different alphabet limit

Codes now run from 1 to a given limit m (for example 30), where m is between 9 and 99. Count how many ways the string can be decoded. For "2727" and m = 30 the answer is 4. Describe your approach, then write it if you like.

Compare with our answer

The upper bound for two-digit pieces changes to m, and the lower bound becomes "no leading zero" (the original 10 was just the smallest two-digit number without one).

def decode_limit(s, m):
    ways = [1] + [0] * len(s)
    for i in range(1, len(s) + 1):
        if s[i - 1] != "0":
            ways[i] += ways[i - 1]
        if i > 1 and s[i - 2] != "0" and int(s[i - 2:i]) <= m:
            ways[i] += ways[i - 2]
    return ways[len(s)]

decode_limit("2727", 30) is 4, decode_limit("1111", 26) is 5 and decode_limit("2727", 26) is 1. Time O(n), space O(n).

A strong answer mentions: the same two cases (one digit, two digits), a leading-zero test for two-digit pieces, comparing against m instead of 26, and ways[0] = 1.

Check what stuck

1. A message of up to 100 digits uses codes 1 to 26, and you must count how many readings it has. Which approach fits best?

2. What does ways[i] mean in the shown code, and why is ways[0] equal to 1?

3. A learner removes the if s[i - 1] != "0": test and always adds ways[i - 1]. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.