Decode ways and string partition DP

Why this matters

Many programs read a string and cut it into pieces. A phone keypad reads digits and cuts them into words. A parser reads a line of text and cuts it into tokens. A spell checker tests whether a long word can be split into known words. In each case the program has to decide where each piece ends, and the number of possible cuts can grow very large.

This lesson solves one such problem. Given a string of digits, count how many ways it can be read as letters. The method is called string partition DP. A partition is a way of cutting a string into pieces. DP, short for dynamic programming, means solving smaller questions once and reusing their answers. Here the smaller questions are "how many ways can the first few digits be read?"

The memoization lesson and the Fibonacci lesson are the background. Decode ways looks like Fibonacci with rules attached, and the same two-variable trick from the previous lesson applies at the end. This lesson stays on the counting problem and the rules. The later lessons on word break and palindrome partitioning use the same pattern with different rules for what counts as a valid piece.

You need to know for loops, std::string, std::vector, and how to read a char such as '7' as a number. The code uses std::string_view, a light way to pass a string to a function without copying it. Read it as "a read-only view of some text".

The mapping

Letters are given numbers. A is 1, B is 2, and so on up to Z is 26. A string of digits is a code for letters when it can be cut into pieces, where each piece is a number from 1 to 26.

Take the string "12". It can be read two ways:

• As 1 then 2. The digit 1 is A and the digit 2 is B. The result is AB.
• As 12 as one piece. The number 12 is L. The result is L.

So "12" has 2 ways. Each way is a different cut of the string. Counting the ways means counting the cuts that produce valid pieces.

The question is not "what does the string say?". It is "how many different cuts are valid?" A cut is valid only when every piece is a code from 1 to 26. This is why the rules matter. A piece of "0" is not a code, because there is no letter 0. A piece of "30" is not a code, because the largest code is 26.

Step 1: the simple cases

Start with short strings and count by hand. Each position in the string can end a piece on its own, or it can end a piece together with the digit before it.

For "1", there is one way, A. For "2", one way, B. For "0", there is no way, because 0 is not a code. For "7", one way, G.

For "26", there are two ways: 2 then 6 gives BF, and 26 as one piece gives Z. Both are valid, so the answer is 2.

For "27", there is one way. The digit 2 alone is B, and the digit 7 alone is G, giving BG. The piece 27 is not valid because it is larger than 26. So the answer is 1.

Notice the pattern. Each digit is a piece by itself in one way, if it is not zero. The last two digits can also be one piece in another way, if that two-digit number is from 10 to 26. Every valid reading comes from one of these two choices at the end.

Step 2: think about the end of the string

Look at the last piece of any valid cut. It is either the last digit alone, or the last two digits together. Nothing else is possible, because a piece is at most two digits long.

If the last piece is the last digit alone, the rest of the string must be a valid cut too. So the number of ways is at least the number of ways for the string without its last digit.

If the last piece is the last two digits together, the rest of the string is the string without its last two digits. So that choice adds the number of ways for the string without its last two digits.

This gives a rule for the total. Let ways(n) mean the number of ways to read the first n digits. Then:

ways(n) = ways(n - 1), if digit n is not 0
        + ways(n - 2), if digits n - 1 and n form 10 to 26

Each part is added only when its condition holds. The number of ways for the empty string is 1, because there is exactly one way to cut nothing: cut nothing at all. That base case is what lets the rule start.

This rule is a recursive function. It works, but it repeats the same work. The same prefix is counted many times when different cuts lead to it. That is the same problem that memoization fixes, and the next step fixes it with a table.

Step 3: fill a table from the start

Store the answer for each prefix in a table called dp. The value dp[i] is the number of ways to read the first i digits of the string. The table has one more entry than the string has digits, because dp[0] is for the empty prefix.

Work through "226" by hand. The digits are 2, 2, 6 at positions 1, 2, 3 of the string.

Read the last row. The digit 6 alone is valid, and the first two digits can be read in 2 ways, BB and V. That gives 2 ways ending in F: BBF and VF. The two-digit 26 is valid, and the first digit can be read in 1 way, B. That gives BZ. The total is 3.

The answer is in dp[3], the last cell. Every cell is filled from cells that come before it, so the table is complete when the loop ends.

Step 4: the zero rules

Zeros cause most of the mistakes in this problem. The digit 0 is not a letter, and it cannot start a code by itself. The rules are short, and each one matters.

A single digit 0 cannot be a piece. So "0" has 0 ways and "10" cannot cut the 0 off alone. The zero must join the digit before it to form 10 or 20. That is the only valid use of a zero.

A two-digit piece cannot have a leading zero. The string "06" would be read as the number 6, but the leading zero is not a code, so "06" has 0 ways. The two-digit check only accepts numbers from 10 to 26, which automatically rejects anything starting with 0.

A two-digit piece cannot be larger than 26. So "30" and "27" are not valid as one piece. For "30", the 3 alone is C, but the 0 cannot stand alone, so the whole string has 0 ways.

Here are the examples worked through the table. Each one uses the same rule from Step 2.

• "100" has 0 ways. The last 0 cannot stand alone, and the pair 00 is not 10 to 26. So the last digit can never be placed, and the answer is 0.
• "2101" has 1 way, BJA. The pieces are 2, 10, 1. The cut 21 followed by 01 fails, because 01 has a leading zero. The cut 2 then 1 then 01 fails for the same reason. So only one cut works.
• "1020" has 1 way, JT. The pieces are 10 and 20. Any other cut leaves a zero alone or makes a piece larger than 26.

Step 5: the code

The rules become three checks inside the loop: the single digit must be from 1 to 9, the two-digit number must be from 10 to 26, and the table is filled in order. The program also checks its own answers. It compares the table method with a plain recursive method on every digit string of length 0 to 5, which is 111,111 strings.

The recursive method is called brute in the code. It tries each cut directly, so it is slow for long strings, but it is simple enough to trust. Testing a fast method against a simple one is the usual way to gain confidence in a DP solution.

#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>
 
// dp[i] = number of ways to decode the first i characters of s.
std::uint64_t num_decodings(std::string_view s) {
    for (char c : s) {
        if (c < '0' || c > '9') {
            throw std::invalid_argument("input must contain only digits");
        }
    }
    std::size_t n = s.size();
    std::vector<std::uint64_t> dp(n + 1, 0);
    dp[0] = 1;  // the empty prefix has one way: decode nothing
    for (std::size_t i = 1; i <= n; ++i) {
        // Option 1: the last character alone is a code (1 to 9, never 0).
        if (s[i - 1] != '0') {
            dp[i] += dp[i - 1];
        }
        // Option 2: the last two characters form a code (10 to 26).
        if (i >= 2) {
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}
 
// Brute force: try every way to cut s into pieces of length 1 or 2.
std::uint64_t brute(std::string_view s) {
    if (s.empty()) {
        return 1;
    }
    std::uint64_t total = 0;
    if (s[0] != '0') {
        total += brute(s.substr(1));
    }
    if (s.size() >= 2) {
        int two = (s[0] - '0') * 10 + (s[1] - '0');
        if (two >= 10 && two <= 26) {
            total += brute(s.substr(2));
        }
    }
    return total;
}
 
int main() {
    const char* examples[] = {"12", "226", "06", "10", "0", "111", "2101", "100", "27"};
    for (const char* e : examples) {
        std::cout << "\"" << e << "\" -> " << num_decodings(e) << '\n';
    }
 
    // Exhaustive check: every digit string of length 0 to 5.
    std::uint64_t checked = 0;
    bool ok = true;
    std::vector<std::string> level{""};
    for (int len = 0; len <= 5; ++len) {
        for (const std::string& s : level) {
            ++checked;
            if (num_decodings(s) != brute(s)) {
                ok = false;
                std::cout << "mismatch on \"" << s << "\"\n";
            }
        }
        std::vector<std::string> next;
        for (const std::string& s : level) {
            for (char d = '0'; d <= '9'; ++d) {
                next.push_back(s + d);
            }
        }
        level = std::move(next);
    }
    std::cout << "checked " << checked << " strings, all match: " << (ok ? "yes" : "no") << '\n';
 
    try {
        num_decodings("1a2");
    } catch (const std::invalid_argument& e) {
        std::cout << "error: " << e.what() << '\n';
    }
    return 0;
}

Compile with the warnings on and run:

g++ -std=c++20 -Wall -Wextra -O2 -o decode decode.cpp
./decode

The real output is:

"12" -> 2
"226" -> 3
"06" -> 0
"10" -> 1
"0" -> 0
"111" -> 3
"2101" -> 1
"100" -> 0
"27" -> 1
checked 111111 strings, all match: yes
error: input must contain only digits

The nine examples match the hand counts above. The line checked 111111 strings is the sum of 10 to the power 0 through 10 to the power 5. The table method and the brute force agree on all of them.

The check at the start of num_decodings throws an error for input that is not all digits. The loop itself assumes digits, because s[i - 2] - '0' only gives the right number for digit characters. A check at the boundary of the function keeps the loop simple.

Example 2: longer strings and many ways

The count grows fast when many digits are 1 or 2, because many cuts are valid. Take the string "1111", four ones. Each 1 can stand alone, and any two neighbouring ones form 11, which is valid. The table shows how the count builds up.

Each value is the sum of the two before it, so the answer for a string of n ones follows the Fibonacci numbers. "1111" gives 5. The full list of readings for "1111" is AAAA, AAK, AKA, KAA, and KK.

This also gives an upper limit. Each reading is a cut of the string into pieces of length 1 or 2. For a string of length n, there are at most F(n + 1) such cuts, where F is the Fibonacci numbers from the previous lesson. For n = 90, that is F(91), which is 4660046610375530309. That number fits in a 64-bit unsigned integer, so std::uint64_t is enough for any string of 90 digits or fewer.

Example 3: a string with zeros in the middle

Zeros in the middle of a string are the hardest case, because they force the cut to be exact. Take "11106". Its answer is 2. The readings are AAJF and KJF.

Check the cut by hand. The digits are 1, 1, 1, 0, 6. The 0 at position 4 must join the digit before it, so the piece is 10, which is J. The 6 at the end is a letter by itself, F. That leaves the first two digits, 1 and 1, to be cut before the 10, which uses the third 1. The cuts are 1 1 10 6, which is A A J F, and 11 1 ... is not possible, because the 0 would then have to join the 1 before it, which already stands alone. The other valid cut is 11 10 6, which is K J F. These two readings are the only ones.

Notice that the table handles this without special cases. At the position of the 0, the single-digit option gives nothing, so only the two-digit option adds to the table. The rule applies everywhere.

Common mistakes

Counting a zero as a letter. A version that always counts the last character alone, and accepts two-digit pieces from 1 to 26 instead of from 10 to 26, looks like this:

std::uint64_t naive(std::string_view s) {
    std::size_t n = s.size();
    std::vector<std::uint64_t> dp(n + 1, 0);
    dp[0] = 1;
    for (std::size_t i = 1; i <= n; ++i) {
        dp[i] += dp[i - 1];  // always counts the last character alone
        if (i >= 2) {
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 1 && two <= 26) {  // accepts "06" as 6
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}

Its real output on four inputs is:

naive "0" = 1
naive "06" = 2
naive "100" = 2
naive "12" = 2

The first three answers are wrong, because the correct answers are 0, 0 and 0. The last answer, for "12", is right, which is why this mistake is easy to miss. Test strings with zeros to catch it.

Using a 32-bit counter. The number of ways grows like Fibonacci, so a long string can overflow a 32-bit integer. Running the same correct rules with std::uint32_t in place of std::uint64_t for the table prints:

narrow (32 bit) all-ones length 50 = 3185141890
wide (64 bit)  all-ones length 50 = 20365011074

The 32-bit answer is wrong. It is the true value with the top bits lost. The 64-bit answer is correct, and Python confirms that F(51) is 20365011074. Nothing warns you when this happens, so pick the counter size from the length limit, using the bound from Example 2.

Starting the table at the wrong value. The base case must be dp[0] = 1. If dp[0] is 0, every entry is built from zeros, so every answer is 0, including "12". A quick check with "1" and "12" catches this.

Forgetting the leading zero check. The two-digit rule says 10 to 26. A rule that says 0 to 26 accepts "06" as a valid code. The check two >= 10 prevents this, so keep it.

Reading a digit character as a number. The character '7' is not the number 7. In C++, '7' - '0' is the number 7, but '7' alone is a character code of 55. Writing s[i] * 10 without subtracting '0' gives a wrong value and no warning.

Practice

Exercise 1. Count the ways to decode "1212" by filling the table by hand. Then list every reading.

Show the answer

The answer is 5. The table is: dp[0] = 1, dp[1] = 1, dp[2] = 2 (1 then 2, and 12), dp[3] = 3 (1 alone from dp[2], and 21 from dp[1]), dp[4] = 5 (2 alone from dp[3], and 12 from dp[2]). The readings are ABAB, ABL, AUB, LAB, and LL. The word AUB uses 21, which is U.

Exercise 2. Explain why "0012" has 0 ways, without counting the table.

Show the answer

The first digit is 0. A 0 cannot stand alone, and the piece 00 is not from 10 to 26, so no cut can start the string. Every reading needs a valid first piece, and there is none, so the answer is 0.

Exercise 3. Write a version of num_decodings that uses two variables instead of the dp vector. Check it against the table method on every digit string of length 0 to 6.

Show the answer

The table needs only the last two values, so two variables hold them. The code below is one way to write it. Its check reports 0 mismatches over 1,111,111 strings, and its answer for twenty ones is 10946, which is F(21) in the numbering where F(0) is 0.

#include <cstdint>
#include <string_view>
 
std::uint64_t num_decodings_o1(std::string_view s) {
    std::uint64_t two_back = 1;  // dp[i - 2], starts as dp[-1] (unused at i = 1)
    std::uint64_t one_back = 1;  // dp[i - 1], starts as dp[0]
    for (std::size_t i = 1; i <= s.size(); ++i) {
        std::uint64_t current = 0;
        if (s[i - 1] != '0') current += one_back;
        if (i >= 2) {
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 10 && two <= 26) current += two_back;
        }
        two_back = one_back;
        one_back = current;
    }
    return one_back;
}

The space is O(1) because the function never grows with the input. This is the same trick as the Fibonacci lesson, and the time is still O(n).

Exercise 4. List every reading of "226", then check that your list has 3 entries.

Show the answer

The three readings are BBF (cut as 2, 2, 6), VF (cut as 22, 6), and BZ (cut as 2, 26). The count is 3, which matches the table.

Exercise 5. The string "1020" has 1 way. Change one digit so that the new string has exactly 2 ways, and explain why it works.

Show the answer

Change the last digit from 0 to 6, giving "1026". The 0 in position 2 must join the 1 before it, giving 10. Then the rest is 26, which can be cut two ways: as 2 then 6, or as 26. So the readings are JBF (cut as 10, 2, 6) and JZ (cut as 10, 26). In "1020", the last digit 0 cannot stand alone, so the string can only end with the piece 20. Changing that 0 to 6 makes the last digit a valid single code, which adds a second way to end the string. The count is 2.

Summary

• A string partition count is built with a table where dp[i] counts the ways to read the first i characters.
• The last piece is either one digit or two digits, so each entry adds at most two earlier entries.
• Zeros are the main source of errors: a 0 must join the digit before it to form 10 or 20, and nothing else.
• The counts grow like Fibonacci numbers, so use a 64-bit counter and check the length limit.
• Test the table method against a simple recursive method on every short string, because the rules have many edge cases.