Start learning free

LESSON 445 OF 535 · DYNAMIC PROGRAMMING

Decode Ways in C++: O(n) Dynamic Programming over Prefixes

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

    C++ · DYNAMIC PROGRAMMING

    Decode Ways in C++, explained

    Problem overview

    The method numDecodings receives a string s of digits. A message of capital letters was turned into digits by writing each letter 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, and turn each group back into a letter. A group can't start with 0: "06" is not "6", and no letter is 0. The method returns how many different ways the string can be decoded, or 0 when it can't be decoded at all.

    For "12" the answer is 2: the groups 1, 2 give "AB" and the group 12 gives "L". For "226" the answer is 3: 2, 26 gives "BZ", 22, 6 gives "VF", and 2, 2, 6 gives "BBF". For "06" the answer is 0, because the first group would have to start with 0.

    Approach: count the ways for each prefix

    Trying every split is a recursion that branches at each position, and it repeats the same sub-problems many times. The better idea is to count decodings of every beginning of the string, from the shortest to the longest.

    Let dp[i] be the number of ways to decode the first i digits. Look at the end of those i digits. The last group is either one digit or two:

    • One digit: the last digit s[i - 1] is a letter on its own when it is 1 to 9. Then every decoding of the first i - 1 digits, followed by that letter, is a decoding of the first i digits. This adds dp[i - 1].
    • Two digits: the last two digits form a letter when they make a number from 10 to 26. Then every decoding of the first i - 2 digits, followed by that letter, counts. This adds dp[i - 2].

    The two cases can both apply, and they never produce the same decoding, because the last group has a different length. If neither applies, dp[i] is 0, and since later entries are built from earlier ones, a block that can't be decoded makes the counts built on it 0 as well. The table needs a starting point: dp[0] is 1 for the empty beginning, which has one decoding with no letters, and that value is what every longer decoding is built on.

    Here is the table for a few inputs, as the code fills it. The first entry is dp[0]:

    "12"     1 1 2
"226"    1 1 2 3
"11106"  1 1 2 3 2 2
"06"     1 0 0

    For "226": dp[1] is 1 (just "2"). For dp[2], the last digit 2 is a letter, adding dp[1], and 22 is a letter, adding dp[0], so it is 2. For dp[3], the last digit 6 adds dp[2] and 26 adds dp[1], so 2 + 1 = 3. The final entry, 3, is the answer. For "11106", the 0 can't stand alone, so dp[4] only gets the two-digit group 10, and dp[5] only gets the single 6 added to dp[4], because 06 is not a letter. The answer is 2.

    Step by step

    1. Store the length of s in int n = s.size().
    2. Create the table. vector<int> dp(n + 1, 0) has one more entry than there are digits, because dp[0] stands for the empty beginning.
    3. Set dp[0] = 1. The empty beginning counts as one way, not zero, or every longer count would stay 0.
    4. Handle the first digit. If s[0] != '0', set dp[1] = 1. A single digit 1 to 9 is a letter. A string that starts with 0 leaves dp[1] at 0, and every count built on it stays 0.
    5. Loop with i from 2 while i <= n. The first two entries are known, each later entry needs the two before it, and the loop ends with dp[n], for the whole string.
    6. Add the one-digit case. If s[i - 1] != '0', do dp[i] += dp[i - 1].
    7. Read the last two digits as a number. int two = stoi(s.substr(i - 2, 2)). The call substr(i - 2, 2) takes two characters starting at position i - 2.
    8. Add the two-digit case. If two >= 10 && two <= 26, do dp[i] += dp[i - 2]. A pair below 10 starts with 0 (like 07) and is no letter, and neither is 27 or more.
    9. Return dp[n] after the loop.

    The solution in C++

    class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        if (s[0] != '0') {
            dp[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int two = stoi(s.substr(i - 2, 2));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

    The C++ details worth a closer look:

    • Characters and digits. s[i - 1] is a char, so it is compared with the character '0' in single quotes, not the number 0. The check s[i - 1] != '0' is true for the digits '1' to '9'.
    • substr and stoi. s.substr(pos, len) returns a new string of up to len characters starting at pos. stoi converts it to an int, and leading zeros are fine: stoi("06") is 6. That is why the range test two >= 10 is needed, since "06" would otherwise pass as a letter.
    • The vector constructor. vector<int> dp(n + 1, 0) makes n + 1 elements, all 0. Writing vector<int> dp{n + 1, 0} with braces would instead make a vector of two elements.
    • Passing the string by value. numDecodings(string s) receives a copy. That is cheap here (at most 100 characters), and the method doesn't change it.
    • Size and the first digit. The lesson guarantees at least one character. Reading s[0] and writing dp[1] on an empty string would go outside the vector, which is undefined behaviour.
    • Overflow. The counts are int. The statement promises that the answer fits in 32 bits, so no wider type is needed. In general, a string like "1111111111" grows the count like the Fibonacci numbers, and a very long input would overflow a signed int, which is undefined behaviour.

    Complexity

    Time: O(n). The loop runs n - 1 times and each pass does a constant amount of work: two comparisons, one two-character substr and one stoi.

    Space: O(n). The table has n + 1 integers. Because each entry uses only the previous two, two variables could replace the table and bring the space down to O(1), but the table is easier to read.

    Edge cases and common mistakes

    • A leading zero. "06" and "0" give 0. No letter is 0 and a group can't start with it, so dp[1] stays 0.
    • A zero in the middle. A 0 can only be the second digit of 10 or 20. "10" gives 1 (only "J"), while "100" gives 0, since the last 0 has no digit to pair with. "30" gives 0 as well, because 30 is too large and 0 is no letter.
    • A single digit. "7" gives 1. The loop doesn't run, and dp[1] is already set.
    • Numbers above 26. "27" gives 1: the two digits are not a letter, but 2 and 7 are. The test two <= 26 matters.
    • Zeros after other digits. "2101" gives 1: the only valid split is 2, 10, 1.
    • Starting dp[0] at 0. Every count is built from it, so the whole table would stay 0.
    • Using only the two-digit number. Skipping the check of the last single digit counts "06" as the letter 6, and gives wrong answers for strings with zeros.
    • An off-by-one on substr. The two digits ending at the ith digit start at index i - 2, not i - 1.

    Testing

    • s = "12" gives 2.
    • s = "226" gives 3.
    • s = "06" gives 0.
    • s = "11106" gives 2.
    • s = "10" gives 1.
    • s = "100" gives 0.
    • s = "0" gives 0.
    • s = "7" gives 1.
    • s = "27" gives 1.
    • s = "2101" gives 1.
    • s = "30" gives 0.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free