Decode Ways

Q: How do you handle zeros in Decode Ways?

A 0 can never be a letter on its own, so it must pair with the digit in front of it, and only 10 and 20 are codes. In the bottom-up loop that means a 0 adds nothing for the one-digit case and adds the count from two digits back only after a 1 or a 2. A leading 0 , two zeros in a row, or a 0 after a digit from 3 to 9 makes the answer 0.

MediumDynamic programming

+10

A message of capital letters was turned into digits with the code A = 1, B = 2, and so on up to Z = 26, and the codes were written one after another with no separators. You get the digit string s. Return how many different messages could have produced it.

Every letter is read from one digit or from two digits next to each other, and a code never starts with 0: 06 is not 6, and a 0 on its own is not a letter. If no reading works, return 0.

Function

numDecodings(s: string) → integer

sstring: the digit string to decode
Returnsinteger: the number of letter messages that encode to s

Constraints

1 ≤ s.length ≤ 100
s holds only the digits 0 to 9, and it may start with 0.
Every prefix and every suffix of s has fewer than 2³¹ readings, 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) and 26 11 (ZK). The middle digits never pair, because 61 is larger than 26.

Input: s = "1203"
Output: 1
Explanation: The 0 has to pair with the 2 in front of it as 20, which forces the reading 1 20 3 (ATC). Reading 12 first would leave the 0 alone, and 03 starts with 0.

Input: s = "06"
Output: 0
Explanation: The first letter would have to start with 0. A lone 0 is not a letter and 06 is not a code, so no message gives this string.

+25 hidden tests on Submit

Follow-up

What if s may also hold *, which stands for any digit from 1 to 9? Can you count the readings in O(n) time, returning the count modulo 10^9+7?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each digit either is a letter on its own or joins its neighbour in a two-digit letter, so the number of readings grows like the Fibonacci numbers: 45 ones already have 1836311903 of them. Listing the readings is hopeless. What cracks the problem is that the number of ways to finish a reading depends only on the position you have reached, so every position needs counting once. The zeros are where the care goes: a 0 can only be the second digit of 10 or 20.

Try both readings with recursion

Correct, but does not finish on the largest tests

Intuition

Stand at index i and look at the next digit. If it is 0, no letter starts here and this path gives no readings. Otherwise you can read that digit as one letter and count the readings of the rest from i+1. If it forms a number from 10 to 26 with the digit after it, you can also read both as one letter and count from i+2. The two choices give different first letters, so their counts add up without overlap. When i reaches the end of the string, you have finished one complete reading, so you return 1.

On "2611": the first letter is 2 or 26. After 2 the next letter must be 6, because 61 is too big. Both branches then end with 1 1 or 11, so the total is 2 × 2 = 4.

The answer is right, but nothing is remembered. On a string of ones every call branches twice and the calls follow the Fibonacci rule, so 45 ones take about 5 × 10^9 calls. The work does not shrink with the answer either: on 44 ones followed by 55 threes and a final 0, the answer is 0, yet the recursion walks every reading of the ones through all the threes before each path dies at the last digit, about 10^11 calls.

Algorithm

Write a helper waysFrom(i) that counts the readings of the digits from index i to the end.
If i equals the length of s, return 1.
If the digit at i is 0, return 0.
Start with waysFrom(i+1), the readings whose next letter takes one digit.
If digits i and i+1 form a number of at most 26, add waysFrom(i+2). Return 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 over and over. In "11111", the count from index 3 is needed after 1 1 1, after 11 1 and after 1 11, and it comes out the same every time, because it depends only on the digits from index 3 on. Store each count in an array memo the first time you work it out, and read it from there afterwards.

Mark the slots that are not worked out with -1, not with 0. Zero is a real answer here: in a string ending in 30, every position has 0 readings. With 0 as the mark, those positions look unknown on every visit and the recursion is as slow as before.

There are n positions, and each is worked out once with constant work, so the time is O(n). The memo and the call stack each take O(n) space. The calls nest at most 100 deep here, which every language handles.

Algorithm

Make an array memo with one slot per index, all set to -1.
In waysFrom(i), return 1 at the end of the string and memo[i] when it is not -1.
Otherwise count as in the plain recursion: 0 for a 0, else waysFrom(i+1) plus waysFrom(i+2) when the two digits form 10 to 26.
Save the count in memo[i], zero included, and return it.
Return waysFrom(0).

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

Turn the recursion around and count prefixes. Let ways(i) be the number of readings of the first i digits. The last letter of such a reading is either the digit at index i-1 alone, which needs a digit from 1 to 9 and leaves ways(i-1) readings for the rest, or the two digits at i-2 and i-1, which need to form 10 to 26 and leave ways(i-2). So ways(i) is the sum of the parts whose condition holds. The empty prefix has one reading, the empty message, so ways(0) = 1.

Walk "1203". After 1 the count is 1. After 12 it is 2: 1 2 and 12. The 0 cannot stand alone and only 20 works, so the count falls back to the count from before the 2, which is 1. The 3 stands alone and 03 is not a code, so the count stays 1.

Each count looks only two counts back, so two variables, twoBack and oneBack, replace the table. That is one pass with constant work per digit: O(n) time, O(1) space and no recursion at all.

Algorithm

Set twoBack = 0 and oneBack = 1, the count for the empty prefix.
For each index i, start current at 0, and add oneBack if digit i is not 0.
If i ≥ 1, digit i-1 is not 0, and digits i-1 and i form a number of at most 26, add twoBack.
Shift along: twoBack = oneBack, then oneBack = current.
After the last digit, 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

Almost every wrong answer on this problem comes from the zeros or from a memo that forgets.

Treating 0 as a letter, or 06 as 6. A zero can only finish 10 or 20, so "30", "100" and "06" all have 0 readings.
Testing a two-digit piece with ≤ 26 alone. 05 is 5 as a number but is not a code. Check that the first of the two digits is not 0.
Using 0 as the mark for a memo slot that is not worked out yet. Many positions really have 0 readings, so those slots never count as stored and get recomputed on every visit. On 44 ones followed by threes and a final 0, every slot is 0 and you are back to about 10^11 calls.
Reading the digit before index 0. Guard the two-digit check with i ≥ 1: in Python s[-1] silently reads the last digit, and other languages read outside the string.
Turning s into one number. A hundred digits fit in no integer type, and the conversion drops leading zeros, which change the answer. Work digit by digit.
In Lua and R, positions start at 1, so the end of the string is position n+1 and the first two-digit check is at position 2.

Frequently asked questions4

What is the time complexity of Decode Ways?

The bottom-up solution reads each digit once with constant work, so it runs in O(n) time and O(1) extra space. Memoized recursion is also O(n) time but uses O(n) space for the memo and the call stack. 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 size 1 and 2. In Climbing Stairs every step is allowed, so the count is a Fibonacci number. In Decode Ways a one-digit step needs a digit from 1 to 9 and a two-digit step needs a number from 10 to 26, so each term of the sum is added only when its condition holds. A string of ones allows every step, and its counts are exactly the Fibonacci numbers.

How do you handle zeros in Decode Ways?

A 0 can never be a letter on its own, so it must pair with the digit in front of it, and only 10 and 20 are codes. In the bottom-up loop that means a 0 adds nothing for the one-digit case and adds the count from two digits back only after a 1 or a 2. A leading 0, two zeros in a row, or a 0 after a digit from 3 to 9 makes the answer 0.

Can Decode Ways be solved in O(1) space?

Yes. The count for a prefix depends only on the counts for the two prefixes one and two digits shorter, so two variables replace the whole table. Each step computes the new count from them and shifts them along by one position.

Python

def numDecodings(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "2611"

Expected

Decode Ways

Function

Constraints

Examples

Hints

Solution

Try both readings with recursion

Recursion with a memo

Bottom-up with two counters

Pitfalls and edge cases

Frequently asked questions4

Similar problems