DSA Decode Ways

The problem

Decode Ways counts the letter readings of a digit string. Each letter takes a code from 1 to 26. A reading splits the string into codes, and each code names one letter.

The answer is the number of valid readings. A string with no valid split answers 0. The letter A is code 1 and the letter Z is code 26.

cases = [
    ("226", 3),
    ("12", 2),
    ("10", 1),
    ("06", 0),
    ("2101", 1),
]
for s, expected in cases:
    print("string", s, "readings:", expected)

Read one row at a time. The string 226 reads as 2-2-6, as 22-6, and as 2-26. The string 06 has no reading, because 0 starts no code.

Intuition: choose one digit or two at each step

The first idea looks at the first digit. It can stand alone as one code. It can also join the next digit as a pair code.

Each choice leaves a shorter string behind it. The same choice then repeats on that shorter string. The count is the sum over all choices that stay valid.

def splits(s, start=0, parts=None):
    if parts is None:
        parts = []
    if start == len(s):
        print("split:", parts)
        return
    num = int(s[start])
    if num != 0:
        splits(s, start + 1, parts + [num])
    if start + 1 < len(s) and 10 <= int(s[start:start + 2]) <= 26:
        splits(s, start + 2, parts + [int(s[start:start + 2])])

print("splits of 12")
splits("12")
print("splits of 226")
splits("226")

The listing works for short strings. It rebuilds the same tail again and again on longer strings. That repeated work is the trap.

Brute force: count every split, recounting tails

The brute force counts splits with recursion. A call at a position counts the readings of the string from that position. No result is stored, so a shared tail is counted again on every visit.

calls = 0

def count_from(s, i):
    global calls
    calls += 1
    if i == len(s):
        return 1
    total = 0
    if s[i] != "0":
        total += count_from(s, i + 1)
    if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
        total += count_from(s, i + 2)
    return total

for s in ["1111", "111111", "11111111"]:
    calls = 0
    result = count_from(s, 0)
    print("string", s, "readings:", result, "calls:", calls)

The string of ones is the kind case here. Every position still branches, and the calls grow with the length. A stored table removes the recounting.

The optimal solution: count readings prefix by prefix

The state is ways(i), the number of readings of the first i digits. Each new count adds a single-digit step and a pair step, and each step counts only when its code is valid.

A single digit adds ways(i - 1) when the digit is not zero. A pair adds ways(i - 2) when the pair forms a number from 10 to 26. The table starts with ways(0) equal to 1, for the empty prefix.

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

cases = [
    ("226", 3),
    ("12", 2),
    ("10", 1),
    ("06", 0),
    ("2101", 1),
]
for s, expected in cases:
    result = decode_ways(s)
    print("string", s, "->", result, "expected:", expected, "match:", result == expected)

All five cases from the start of the article pass. The zero inside 10 survives inside its pair. The leading zero in 06 kills its string at the first step.

Walkthrough: the table for 226

The walk builds the table one prefix at a time. Each row shows the prefix, the single-digit step, and the pair step.

s = "226"
ways = [1]
print("prefix '' ways 1")
for i in range(1, len(s) + 1):
    total = 0
    single = 0
    pair = 0
    if s[i - 1] != "0":
        single = ways[i - 1]
        total += single
    if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
        pair = ways[i - 2]
        total += pair
    ways.append(total)
    print("prefix", s[:i], "single adds", single, "pair adds", pair, "ways", total)
print("table:", ways)
print("answer:", ways[-1])

The last row reads the answer off the table. The prefix 226 has three readings. They are 2-2-6, 22-6, and 2-26.

Complexity

The table does a fixed amount of work per digit, so its time is O(n) for n digits. The table holds one count per prefix, so its space is O(n).

The brute force stores nothing. Its cost is the call count, and that count grows fast on branching strings.

calls = 0

def count_from(s, i):
    global calls
    calls += 1
    if i == len(s):
        return 1
    total = 0
    if s[i] != "0":
        total += count_from(s, i + 1)
    if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
        total += count_from(s, i + 2)
    return total

for n in [6, 10, 14]:
    calls = 0
    count_from("1" * n, 0)
    print("digits", n, "- brute calls:", calls, " table steps:", n)

The gap widens with each size. The table steps grow in a straight line. The brute calls grow much faster.

Edge cases and pitfalls

The digit zero is never a letter on its own. A zero survives only inside a pair from 10 to 26. A pair above 26 is also invalid, even when both digits are fine alone.

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

print("single zero:", decode_ways("0"))
print("zero with valid pair:", decode_ways("10"))
print("zero with pair too big:", decode_ways("30"))
print("pair too big, singles fine:", decode_ways("27"))
print("zero stranded at the end:", decode_ways("100"))
print("single digit:", decode_ways("7"))

The string 27 shows the careful case. Its pair is invalid, but its single digits still give one reading. Only a zero with no valid pair makes a count fall to zero and stay there.