Decode Ways

The problem

Letters are turned into numbers with A = 1, B = 2, and so on up to Z = 26. Then the numbers are written one after another, with no spaces. You are given such a string of digits digits. Return how many different letter strings could have produced it.

A letter’s number never starts with 0, so “06” is not F. If no letter string fits, return 0.

Example 1

Input: digits = "2261"

Output: 3

2 2 6 1 is BBFA, 22 6 1 is VFA, and 2 26 1 is BZA. 61 is too big to be a letter.

digits

20216213

Example 2

Input: digits = "06"

Output: 0

The first digit is 0, and no letter’s number starts with 0.

Example 3

Input: digits = "110"

Output: 1

The 0 must pair with the 1 before it as 10 (J). So the only reading is 1 10, which is AJ.

Constraints

• 1 ≤ digits.length ≤ 100 (call it n)
• s holds only digits.
• The answer fits in a 32-bit integer.

Clarifying questions

Can 0 be a letter on its own?

No. A 0 must be the second digit of 10 or 20, or there is no decoding.

Is "05" the letter E?

No. A leading zero is not allowed, so "05" is not a letter.

Do we list the decodings?

No, only count them.

Can the string start with 0?

Yes, and then the answer is 0.

Spot the pattern

Look at the next letter. It uses one digit, or two digits that form 10 to 26. Either way, what is left is a shorter version of the same problem. So the count is built from counts of smaller pieces, and those pieces repeat across choices. That is dynamic programming, and it has the same shape as Climbing Stairs, where each step is 1 or 2, but with rules about which steps are allowed.

Solutions

Plain recursionO(2ⁿ)Two numbersO(n)

Show all

There is no middle tab here. Adding a memo to the recursion, or filling a table, costs O(n) time like the two-number version, but O(n) memory. Climbing Stairs shows that step in detail.

Plain recursion O(2ⁿ)

The idea

Let ways(position) count the decodings of the digits from position to the end.

• If position is past the end, all digits are used: that is 1 complete decoding.
• If digits[position] is 0, no letter can start here: 0.
• Otherwise, use one digit as a letter and count ways(position + 1). If the two digits at position form a number from 10 to 26, also use them as one letter and add ways(position + 2).

The answer is ways(0).

Why it is correct: every decoding starts with a one-digit letter or a two-digit letter, never both. So the two calls count two groups that do not overlap and together hold every decoding.

Walkthrough

digits

20216213

1. def ways(position):
2. if position == len(digits): return 1
3. if digits[position] == "0": return 0
4. total = 0
5. total += ways(position + 1) # one digit
6. if digits[position:position+2] is 10 to 26:
7. total += ways(position + 2) # two digits
8. return total

ways(position) counts the decodings of the digits from position on. The next letter uses one digit, then ways(position + 1), or two digits from 10 to 26, then ways(position + 2). Highlighted edges are two-digit letters. w(i) stands for ways(i).

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private String digits;

    // Plain recursion: the next letter uses one digit or two, so add the ways to
    // decode the rest after each choice. The same suffixes are decoded again and again.
    public int numDecodings(String digits) {
        this.digits = digits;
        return ways(0);
    }

    private int ways(int position) {
        // Used up every digit: one complete decoding.
        if (position == digits.length()) return 1;
        // No letter starts with 0.
        if (digits.charAt(position) == '0') return 0;
        int total = ways(position + 1);
        if (position + 1 < digits.length()) {
            int twoDigit = Integer.parseInt(digits.substring(position, position + 2));
            if (twoDigit >= 10 && twoDigit <= 26) total += ways(position + 2);
        }
        return total;
    }
}

Big O

Time O(2ⁿ)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of ways. Each call does a few checks and one or two additions, a fixed job, so each call counts as 1 step.

   1. def ways(position):
   2. if position == len(digits): return 1
   3. if digits[position] == "0": return 0
   4. total = 0
   5. total += ways(position + 1) # one digit
   6. if digits[position:position+2] is 10 to 26:
   7. total += ways(position + 2) # two digits
   8. return total

2. 2 Count the runs on Example 1

   The table counts how often each ways(position) was called. The later positions are reached along several paths, so they are solved again each time.

   1 + 1 + 2 + 3 + 3 = 10 calls.

   call	ways(0)	ways(1)	ways(2)	ways(3)	ways(4)
   times called	1	1	2	3	3

   total

   1 + 1 + 2 + 3 + 3 = 10 calls

3. 3 Write the count for any n

   Each call makes at most 2 calls, and each moves i forward by at least 1. So the tree is at most n + 1 levels deep, and level d has at most 2ᵈ calls:

   1 + 2 + 4 + … + 2ⁿ = 2ⁿ⁺¹ − 1 calls

   Check it with Example 1: 2⁵ − 1 = 31 at most. The real run made 10, because “61” is not a letter, so some calls have only one child. A string like “1111…” makes every call branch.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is 2ⁿ. With 100 digits, far too many.

   So the time is O(2ⁿ).

5. S Space: count the extra memory the same way

   The call stack holds one path at a time, at most n + 1 calls. So the space is O(n).

   call stack (up to n + 1 deep)

Two numbers O(n)

The idea

Turn it around and grow the string from the left. Count the decodings of each prefix: the first digit, then the first two digits, and so on. The last letter of a prefix uses its last digit, or its last two digits:

• If the last digit is not 0, every decoding of the prefix one digit shorter can be extended with it.
• If the last two digits form 10 to 26, every decoding of the prefix two digits shorter can be extended with them.

Add the two. Only the two previous counts are ever needed, so keep them as two_back and one_back. Start with 1 for the empty prefix, and 1 or 0 for the first digit, depending on whether it is 0.

Why it is correct: it applies the same split as the recursion, from the other end, and each count it needs is already known when it is used.

Walkthrough

digits

20216213

1. two_back, one_back = 1, (1 if digits[0] != "0" else 0)
2. for i in 1 .. len(digits) - 1:
3. current = 0
4. if digits[i] != "0": current += one_back
5. if digits[i-1:i+1] is 10 to 26:
6. current += two_back
7. two_back, one_back = one_back, current
8. return one_back

Go left to right and count the decodings of each prefix. The last letter of a prefix uses its last digit, or its last two digits. So a prefix only needs the counts for the prefixes one and two digits shorter.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two numbers, left to right: the ways to decode a prefix come from the prefix
    // one digit shorter and the one two digits shorter. Keep just those two. O(n) time, O(1) space.
    public int numDecodings(String digits) {
        // Ways for the empty prefix, and for the first digit alone.
        int twoBack = 1, oneBack = digits.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < digits.length(); i++) {
            int current = 0;
            // Digit i on its own is a letter, unless it is 0.
            if (digits.charAt(i) != '0') current += oneBack;
            // Digits i - 1 and i together are a letter from 10 to 26.
            int twoDigit = (digits.charAt(i - 1) - '0') * 10 + (digits.charAt(i) - '0');
            if (twoDigit >= 10 && twoDigit <= 26) current += twoBack;
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body does two checks, up to two additions and two moves. That is a fixed job, so each run of the loop counts as 1 step.

   1. two_back, one_back = 1, (1 if digits[0] != "0" else 0)
   2. for i in 1 .. len(digits) - 1:
   3. current = 0
   4. if digits[i] != "0": current += one_back
   5. if digits[i-1:i+1] is 10 to 26:
   6. current += two_back
   7. two_back, one_back = one_back, current
   8. return one_back

2. 2 Count the runs on Example 1

   The loop runs for positions 1, 2 and 3.

   3 runs.

   i	1	2	3
   loop runs	1	1	1

   total

   3 runs

3. 3 Write the count for any n

   The loop goes from 1 to n − 1:

   n − 1 runs

   Check it with Example 1: 4 − 1 = 3. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Three numbers, whatever n is. So the space is O(1).

   two_backone_backcurrent

Common mistake

Treating a 0 like any other digit

A 0 cannot be a letter alone, and a pair like “05” is not a letter either. If the code only checks that a pair is at most 26, “05” passes, and strings like “105” get the wrong count. Check that the pair is between 10 and 26.

Tested at the limits

2,000 random strings of 1 to 16 digits made of 0, 1, 2, 6 and 7, the digits on the edges of the rules. The plain recursion and the two numbers gave the same answer every time.

Largest inputs	Result
100 digits (the most allowed): 44 ones then 56 nines, for 1,836,311,903 ways, which still fits in 32 bits. Two numbers.	Under 0.001 s, and under 0.001 MB of extra memory: just the two numbers.
24 ones. Plain recursion, about 100,000 calls.	0.02 s. Each extra 1 makes about 1.6 times more calls, so 100 digits is far out of reach.