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
0alone being illegal and26being legal but27not. - 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
- 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.
- 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. - Last piece is one digit. If
s[i-1]is not"0", every decoding of the first i − 1 digits extends by that digit: addways[i - 1]. - 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: addways[i - 2]. Checking>= 10rules out"06", which is not a valid code. - 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(1.6^n): every position can branch into two calls | O(n): recursion depth and slices |
| Table (shown code) | O(n): two checks and at most two additions per digit | O(n): the ways list (two variables would give O(1)) |
Edge cases
- A single zero (
"0"): returns0; no letter has code 0. - Leading zero (
"06"): returns0, since"06"is not a code and"0"cannot stand alone. - Zero after a one or two (
"10"): returns1(onlyJ);"100"returns0because the last zero has nothing to pair with. - Number too large (
"27"): returns1, only2and7, because 27 is above 26. - Examples:
"12"returns2,"226"returns3,"11106"returns2. - 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(...) <= 26but 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.
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.
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?
The number of readings of a prefix is the sum of two smaller prefix counts, giving O(n). Greedy reading finds one reading, not the count; listing them can reach 10^20; and counting digits ignores which ones follow.
2. What does ways[i] mean in the shown code, and why is ways[0] equal to 1?
ways[i] counts the readings of the first i digits, and the empty prefix has exactly one (reading nothing), which seeds the sums. A value of 0 would zero every later entry.
3. A learner removes the if s[i - 1] != "0": test and always adds ways[i - 1]. Which input now gives a wrong answer?
For "10" the lone 0 is wrongly treated as a letter, so the count becomes 2 instead of 1. In "12", "226" and "27" there is no zero, so the missing test changes nothing.
Score 60% or more and the lesson is marked complete.