Decode Ways
A message of capital letters was encoded with A = 1, B = 2, and so on up to Z = 26, and the codes were written with no separators. Given the digit string s, return how many messages could have produced it.
A letter is read from one digit or two adjacent digits, and a code never starts with 0: 06 is not 6, and a lone 0 is not a letter. If no reading works, return 0.
Function
- sstring
- the digit string to decode
- Returnsinteger
- the number of letter messages that encode to s
Constraints
1 ≤ s.length ≤ 100sholds only the digits0to9, and it may start with0.- Every prefix and every suffix of
shas fewer than231readings, so the answer and every count you build on the way fit in a signed 32-bit integer.
Examples
- Input
- s = "2611"
- Output
- 4
- Explanation
- The four readings are
2 6 1 1(BFAA),26 1 1(ZAA),2 6 11(BFK) and26 11(ZK). The middle digits never pair, because 61 is larger than 26.
- Input
- s = "1203"
- Output
- 1
- Explanation
- The
0must pair with the2before it as20, which forces1 20 3(ATC). Reading12first would leave the0alone, and03starts with 0.
- Input
- s = "06"
- Output
- 0
- Explanation
- The first letter would have to start with
0. A lone0is not a letter and06is not a code, so no message gives this string.
Follow-up
What if s may also hold *, standing for any digit from 1 to 9? Can you count the readings in O(n) time, modulo 10^9+7?
Hints
Open them one at a time. Each one gives away a little more.
Look at the first digit only. In how many ways can the first letter be read, and what is left of the string after each choice?
How many readings the rest of the string has depends only on where the rest starts, not on how you got there. Count each starting point once and reuse the count.
Let
ways(i)count the readings of the firstidigits, withways(0) = 1. Addways(i-1)when digiti-1is not0, and addways(i-2)when the two digits before positioniform a number from 10 to 26. You only need the last two counts.
Solution
Each digit is a letter alone or joins its neighbour, so the readings grow like the Fibonacci numbers: 45 ones have 1836311903. Listing them is hopeless, but the ways to finish a reading depend only on the position reached, so each position needs counting once. A 0 can only end 10 or 20.
Try both readings with recursion
Correct, but does not finish on the largest tests
Intuition
At index i, a 0 starts no letter, so the path gives no readings. Otherwise read one digit and count the rest from i+1; if the two digits form 10 to 26, also read both and count from i+2. The two choices give different first letters, so their counts add without overlap, and reaching the end completes one reading.
Nothing is remembered, so the calls follow the Fibonacci rule: 45 ones take about 5 × 10^9 calls. An answer of 0 is no faster: 44 ones, 55 threes and a final 0 take about 10^11 calls, since every reading of the ones dies only at the last digit.
Algorithm
waysFrom(i)counts the readings of the digits from indexion.- At the end of the string, return 1. On a
0, return 0. - Otherwise return
waysFrom(i+1), pluswaysFrom(i+2)when digitsiandi+1form a number of at most 26. - The answer is
waysFrom(0).
def numDecodings(s):
n = len(s)
def ways_from(i):
# The number of ways to decode s[i:].
if i == n:
return 1 # nothing left: one finished reading
if s[i] == "0":
return 0 # no letter code starts with 0
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
return ways
return ways_from(0)Recursion with a memo
Intuition
The recursion asks the same question many times. In "11111" the count from index 3 is needed after 1 1 1, after 11 1 and after 1 11, and it is the same each time, because it depends only on the digits from index 3 on. Store each count the first time you compute it, and mark slots not yet computed with -1, since 0 is a real count.
There are n positions, each computed once with constant work: O(n) time. The memo and the call stack take O(n) space, at most 100 calls deep.
Algorithm
- Fill
memowith-1, one slot per index. - In
waysFrom(i), return 1 at the end of the string andmemo[i]when it is not-1. - Otherwise count as in the plain recursion, save the count in
memo[i], zero included, and return it.
def numDecodings(s):
n = len(s)
memo = [-1] * n # memo[i]: ways to decode s[i:], -1 until worked out
def ways_from(i):
if i == n:
return 1
if memo[i] != -1:
return memo[i]
ways = 0
if s[i] != "0":
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
memo[i] = ways
return ways
return ways_from(0)Bottom-up with two counters
Intuition
Count prefixes instead. Let ways(i) be the number of readings of the first i digits. The last letter is either digit i-1 alone, which needs 1 to 9 and leaves ways(i-1) readings, or digits i-2 and i-1 together, which must form 10 to 26 and leave ways(i-2). Add the parts whose condition holds. The empty prefix has one reading, so ways(0) = 1.
On "1203" the counts go 1, 2, then back to 1 at the 0, because only 20 works and it leaves the count before the 2. The 3 stands alone, so the count stays 1. Each count looks two back, so two variables replace the table: O(n) time, O(1) space.
Algorithm
- Set
twoBack = 0andoneBack = 1, the count for the empty prefix. - For each index
i, setcurrenttooneBackif digitiis not0, else to 0. - If
i ≥ 1, digiti-1is not0, and digitsi-1andiform at most 26, addtwoBack. - Shift:
twoBack = oneBack, thenoneBack = current. - Return
oneBack.
def numDecodings(s):
# ways(i) counts the readings of the first i digits; ways(0) = 1.
two_back, one_back = 0, 1 # ways(i-1) and ways(i) before digit i is read
for i in range(len(s)):
current = 0
if s[i] != "0":
current = one_back # digit i is a letter on its own
if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
current += two_back # digits i-1 and i form one letter, 10 to 26
two_back, one_back = one_back, current
return one_back
Pitfalls and edge cases
- Treating
0as a letter, or06as 6."30","100"and"06"all have 0 readings. - Testing a two-digit piece with
≤ 26alone.05is 5 as a number but not a code, so check that its first digit is not0. - Marking unknown memo slots with 0. Positions with 0 readings then never count as stored: on 44 ones, 55 threes and a final
0you are back to about10^11calls. - Reading the digit before index 0. Guard the two-digit check with
i ≥ 1; in Pythons[-1]silently reads the last digit. - Turning
sinto one number. A hundred digits fit in no integer type, and the leading zeros that change the answer are lost.
Frequently asked questions3
What is the time complexity of Decode Ways?
The bottom-up solution reads each digit once with constant work: O(n) time and O(1) extra space. Memoized recursion is also O(n) time but uses O(n) space. Plain recursion is exponential: on a string of ones the number of calls grows like 1.618^n.
How is Decode Ways related to Climbing Stairs?
Both count the ways to cover a line with steps of 1 and 2. In Climbing Stairs every step is allowed, so the counts are Fibonacci numbers. In Decode Ways a one-digit step needs 1 to 9 and a two-digit step needs 10 to 26, so each term is added only when its condition holds.
How do you handle zeros in Decode Ways?
A 0 is never a letter alone, so it must pair with the digit before it as 10 or 20. It adds the count from two digits back only after a 1 or a 2, and nothing otherwise. A leading 0, two zeros in a row, or a 0 after 3 to 9 gives 0.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def numDecodings(s):
# Write code hereTest #1
Test #2
Test #3
Argument
s = "2611"
Expected Output
4