Start learning free

LESSON 446 OF 536 · DYNAMIC PROGRAMMING

Decode Ways in Python: Dynamic Programming in O(n) Time

Practice O(n) Read the full explanation

A message made of the capital letters A to Z was turned into digits by writing each letter as its position in the alphabet: A becomes 1, B becomes 2, and so on up to Z, which becomes 26.

To decode the digits, split them into groups, each group a number from 1 to 26, and turn each group back into its letter. A group can't start with 0: "06" is not the same as "6", and no letter is 0. For example, "11106" can be decoded in two ways:

  • "AAJF", from the groups 1, 1, 10, 6;
  • "KJF", from the groups 11, 10, 6.

The groups 1, 11, 06 don't work, because 06 starts with 0.

Given a string s of digits, return the number of ways to decode it. If it can't be decoded at all, return 0.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1, 2) or as "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: The first group would have to start with 0: "0" is no letter, and "06" can't be read as 6. So "06" can't be decoded.

Constraints:

  • 1 <= s.length <= 100
  • s is made of digits only, 0 to 9, and may start with 0.
  • The answer fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time, where n is the length of s.

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · DYNAMIC PROGRAMMING

    Decode Ways in Python, explained

    Problem overview

    numDecodings receives a string s of digits. Each capital letter was written as its position in the alphabet (A is 1, B is 2, up to Z as 26). To decode, split the digits into groups, each group a number from 1 to 26 that is written without a leading zero, and turn each group into its letter. The function returns how many different ways there are, or 0 when the string cannot be decoded at all.

    For "12" the answer is 2: "AB" (1, 2) or "L" (12). For "226" it is 3: "BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6). For "06" it is 0, because the first group would have to start with 0, and neither 0 nor 06 is a letter.

    Approach: count decodings of every beginning

    Let dp[i] be the number of ways to decode the first i digits of s. The last letter of any decoding of those i digits is made from either the last digit alone or the last two digits, and nothing else is possible. That gives two independent cases, which are added:

    • The last digit is a letter on its own. This works when s[i - 1] is not '0'. Every decoding of the first i - 1 digits, followed by that letter, is a decoding of the first i digits, so add dp[i - 1].
    • The last two digits form one letter. This works when the number they make is from 10 to 26. Every decoding of the first i - 2 digits, followed by that letter, counts, so add dp[i - 2]. A pair such as 07 starts with 0 and is no letter, and 27 or more is beyond Z.

    The table starts with dp[0] = 1: the empty beginning has exactly one decoding, with no letters. Every longer decoding is built on it, so it must count as one way, not zero. Then dp[1] is 1 if the first digit is not '0', and 0 otherwise. A string that starts with 0 stays at 0, and so does everything built on top of it.

    The filled tables for two of the examples:

    s = "226"    dp = [1, 1, 2, 3]
s = "11106"  dp = [1, 1, 2, 3, 2, 2]

    In "226", dp[2] is 2: the digits "22" are "BB" or "V". Then dp[3] adds dp[2] (the 6 on its own) and dp[1] (the pair 26), giving 3. In "11106", the 0 at index 3 cannot stand alone, so dp[4] gets only the pair 10, which adds dp[2] (the two ways to decode "11"). Then dp[5] takes the 6 on its own, adding dp[4], while the pair 06 adds nothing. The result is 2.

    Step by step

    1. Store the length in n = len(s).
    2. Create the table with n + 1 zeros: dp = [0] * (n + 1). One extra entry stands for the empty beginning.
    3. Set dp[0] = 1.
    4. Set dp[1] to 1 when s[0] is not '0'.
    5. Loop over the rest with for i in range(2, n + 1). Each entry needs the two before it, and n + 1 makes dp[n] the last one filled.
    6. Single digit. If s[i - 1] is not '0', add dp[i - 1] to dp[i].
    7. Read the pair. Outside that if, take the last two digits as a number: two = int(s[i - 2:i]).
    8. Two digits. If 10 <= two <= 26, add dp[i - 2] to dp[i].
    9. Return dp[n], the number of decodings of the whole string.

    The solution in Python

    class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        if s[0] != '0':
            dp[1] = 1
        for i in range(2, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            two = int(s[i - 2:i])
            if 10 <= two <= 26:
                dp[i] += dp[i - 2]
        return dp[n]

    Python details worth a closer look:

    • Slices. s[i - 2:i] holds the characters at indices i - 2 and i - 1, the end index being excluded. For "226" and i = 3 it is "26".
    • int accepts a leading zero. int("07") is 7, so a pair with a leading zero turns into a number below 10, which the range check then rejects. That is why the check uses 10 as the lower bound.
    • Chained comparison. 10 <= two <= 26 tests both bounds at once.
    • [0] * (n + 1) builds a list of n + 1 zeros. It is safe here because integers are immutable.
    • Digits are compared as characters. s[i - 1] != '0' compares one-character strings, so there is no need to convert to numbers for the single-digit case.
    • Big counts are fine. Python integers don't overflow. The lesson's answers fit in 32 bits anyway.

    Complexity

    Time: O(n). The loop runs n - 1 times and each pass does a constant amount of work (the two-character slice is always two characters long).

    Space: O(n). The table has n + 1 entries. Since each entry uses only the two before it, two variables could replace the table, but the table makes the idea easier to follow.

    Edge cases and common mistakes

    • A leading zero. "06" and "0" give 0. Here dp[1] stays 0, and for "06" the pair 06 is 6, which is outside 10 to 26.
    • A zero in the middle. "10" gives 1, because 0 can only follow a 1 or a 2 as part of 10 or 20. "100" gives 0: the final 0 has no partner, since the pair 00 is not a letter and the single 0 is not either. "30" gives 0 for the same reason.
    • Pairs above 26. "27" gives 1: only 2 and 7, since 27 is no letter.
    • Starting dp[0] at 0. Every count would stay 0, because everything is built on the empty beginning.
    • A single digit. "1" gives 1. The loop doesn't run, and dp[1] is already set.
    • Checking only the pair. Accepting a pair like 06 as 6 would count a decoding that the rules forbid.

    Testing

    • "12" gives 2.
    • "226" gives 3.
    • "06" gives 0.
    • "11106" gives 2.
    • "10" gives 1.
    • "100" gives 0.
    • "27" gives 1.
    • "2101" gives 1.
    • "1111111111" (ten 1s) gives 89.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free