Decode ways and string partition DP in Python

Why this matters

Many programs read a string of digits and turn it into letters, words or actions. A phone keypad, a message code and a block of encoded data all work this way. Coding interviews use the same idea in a counting form: given a string of digits, how many different ways are there to read it as letters?

This problem is a good first example of string partition DP. In that pattern you cut a string into pieces, and the table records the number of valid ways to cut each prefix. The one-row table from the one-dimensional DP lesson still works here. Each cell depends on one or two cells before it, which is what makes the two-variable trick possible.

The word break lesson later in this module also cuts a string into pieces, but its pieces must appear in a dictionary. Here the pieces are fixed by a rule: one digit or two digits, with conditions on the value.

Every program here is a plain Python file. The programs marked python run print their output without reading input. Run any file with python3 main.py. The outputs shown were produced on Python 3.14.

The problem

Map each number to a letter: 1 is A, 2 is B, and so on up to 26 is Z. A string of digits can be read in more than one way, because a two-digit number such as 12 can be read as one code or as two.

Take the string "12". It can be read as 1 then 2, which gives AB. It can also be read as 12, which gives L. So there are 2 ways.

Take the string "226". It can be read as 2 2 6, which gives BBF. It can be read as 22 6, which gives VF. It can be read as 2 26, which gives BZ. So there are 3 ways.

The task is to count the ways, not to list them. The count can get very large, so the solution has to avoid trying every split one by one.

Step 1: Each position is a choice

Read the string from left to right. At each point, the next code is either one digit or two digits. Two rules decide which choices are allowed.

• A single digit is valid when it is 1 to 9. The digit 0 has no letter on its own, so "0" alone is not valid.
• Two digits are valid when their value is 10 to 26. The value must be written without a leading zero. So "06" is not valid, because its value is 6 and it has a leading zero. The value 10 is valid as the code for J, and 20 is valid as the code for T. The value 27 is not valid, because it is above 26.

These two rules give most of the difficulty. Here are some short cases.

• "0" has 0 ways. Nothing can be read from it.
• "10" has 1 way, which is 10 read as J. Reading the 1 alone leaves a lone zero, which cannot be read.
• "100" has 0 ways. The 1 cannot pair with the first 0, which would make 10, and then the second 0 is left alone. The 1 alone leaves 00, which cannot be read.
• "30" has 0 ways. The 3 can stand alone, but the 0 cannot. The pair 30 is above 26.

Step 2: The table

Define dp[i] as the number of ways to read the first i characters of the string. The empty prefix, with i = 0, has one way to read it: read nothing. So dp[0] = 1.

To work out dp[i], look at the last piece. It is either a one-digit piece or a two-digit piece.

• If the last character is 1 to 9, it can be a one-digit piece. That adds dp[i - 1], the number of ways to read everything before it.
• If the last two characters form a value from 10 to 26, they can be a two-digit piece. That adds dp[i - 2], the number of ways to read everything before those two characters.

So the recurrence is:

dp[i] = (dp[i - 1] if the last character is 1 to 9)
      + (dp[i - 2] if the last two characters are 10 to 26)

Here is the full trace for the string "2261". Each row is one character.

The answer for "2261" is 3. The three readings are 2 26 1 which gives BZA, 22 6 1 which gives VFA, and 2 2 6 1 which gives BBFA.

The code

The code below builds the table as a list. The variable c is the current character. The value two is the number made by the last two characters. Python's int(...) turns a one-character string such as "2" into the number 2, so int(s[i - 2]) * 10 + int(c) gives the two-digit value.

Output:

'12' 2 2
'226' 3 3
'06' 0 0
'10' 1 1
'100' 0 0
'2261' 3 3
'11106' 2 2
'0' 0 0
'' 1 1
'27' 1 1

Each test string gives the same answer from the list and from the two-variable loop. The empty string gives 1 because dp[0] is 1. A caller that treats empty input as an error should check for it before calling the function.

The check for a leading zero is in the range test. The value of "06" is 6, which is outside 10 to 26, so it is not counted. The single-digit check c != "0" handles a lone zero.

Step 3: Two variables are enough

Each cell of the table reads only the two cells before it. So the code needs only dp[i - 1] and dp[i - 2]. In the second function, prev1 holds dp[i - 1] and prev2 holds dp[i - 2]. At the end of each loop step, prev1 moves into prev2, and the new value becomes prev1.

The start needs care. Before the first character, prev1 is dp[0], which is 1. The variable prev2 is not read on the first step, because the two-digit check needs i >= 2. On the second step, prev2 holds dp[0], which is the correct value for dp[i - 2].

The memory use is now constant. The time is O(n) for a string of length n, because the loop reads each character once.

Step 4: The general shape of string partition DP

The same shape works for any rule that cuts a string into pieces. Let the state be the length of the prefix that has been read. For each prefix length i, look at each piece length L that is allowed to end at position i. Add the count for the prefix before that piece.

dp[0] = 1
for each prefix length i from 1 to n:
    for each allowed piece length L ending at i:
        dp[i] += dp[i - L]

Decode ways is this shape with two piece lengths, 1 and 2, and a rule for each. A dictionary word break uses the same shape, with the allowed pieces coming from a set of words. Palindrome partitions use it with a rule about reading the piece forwards and backwards.

Step 5: Large inputs and exact counts

The count can grow very fast. A string of n ones has F(n + 1) ways, the Fibonacci number at that position. Each extra digit adds a larger number. Python integers have no fixed size, so the function gives an exact count for any length. The program below counts the ways for strings of ones, and it also shows the result a 64-bit integer would give. The second value is computed by keeping only the low 64 bits of the exact number, which is what a Java long does.

Output:

n=91 64-bit=7540113804746346429 exact=7540113804746346429
n=92 64-bit=-6246583658587674878 exact=12200160415121876738
n=93 64-bit=1293530146158671551 exact=19740274219868223167
n=100 64-bit=1298777728820984005 exact=573147844013817084101

Up to n = 91 the 64-bit value is exact. From n = 92 on, the value is larger than a 64-bit integer can hold, so the wrapped number can become negative. In Python you get the exact value unless you choose a fixed-size type yourself. When a problem asks for an exact count, keep the Python integer. When a problem asks for the count modulo a number, take the remainder with % after each addition, as in the matrix lesson.

Common mistakes

Making the list one element too short. The table needs n + 1 cells, one for each prefix length from 0 to n. If you write dp = [0] * n, the last step tries to write past the end.

def count_wrong_off_by_one(s):
    n = len(s)
    dp = [0] * n
    dp[0] = 1
    for i in range(1, n + 1):
        c = s[i - 1]
        if c != "0":
            dp[i] += dp[i - 1]
    return dp[n]
 
 
print(count_wrong_off_by_one("12"))

Output:

  File "main.py", line 8, in count_wrong_off_by_one
    dp[i] += dp[i - 1]
    ~~^^^
IndexError: list index out of range

The last line names the error, and the caret line points at the index that was too big. The line above it is the line in your file where the problem happened, and the file path on your machine will differ. The fix is to create the list with n + 1 elements.

Forgetting the zero rule. If you add dp[i - 1] for every character, a zero adds ways it should not. The code below is the table version without the check c != "0".

Output:

no zero check: 10 -> 2 , 30 -> 1

The correct answers are 1 for "10" and 0 for "30". The program prints no error, so the mistake is easy to miss. The string "10" gets an extra way from a lone zero, and "30" gets a way from a lone zero. Test strings that contain zeros, such as "10", "20", "30" and "100", on every change.

Accepting a leading zero in the two-digit value. A common shortcut takes the two characters as a string, converts them with int, and checks that the number is from 1 to 26. That is wrong, because int("06") is 6, which is in range.

Output:

parse '06' gives 1

The correct answer is 0. The range must be 10 to 26, not 1 to 26. A value of 1 to 9 as a two-digit piece is always a leading zero followed by a digit, and a pair like 06 must not count.

Reading a character before the start of the string. When i is 1, the expression s[i - 2] asks for index -1. In Java this stops the program. In Python, a negative index counts from the end of the string, so no error is raised. The character read is the last one in the string, and the answer is wrong. The check if i >= 2: must come before any use of the previous character. The next program has no such check, and it gives 2 for the string "1", where the correct answer is 1.

Output:

no guard '1': 2

For "1", the first step reads s[-1], which is the same character "1". That makes the two-digit value 11, which looks valid, and it adds dp[-1], which is the last cell of the list. This is why an answer can look plausible while being wrong. Keep the guard.

Letting the number overflow. As Step 5 showed, the count grows quickly. A 64-bit integer wraps around silently once the value is too large, and Java's long does the same. Python integers do not wrap, so this mistake is about other languages and about fixed-size types inside libraries. Use the modulo the problem asks for when the statement gives one.

Practice

Exercise 1. Count the ways to decode "111".

Show the answer

3. The readings are 1 1 1, 11 1 and 1 11. Each is valid, so the count is 3.

Exercise 2. Count the ways to decode "2020".

Show the answer

1. Trace the table. The first 2 gives dp[1] = 1. The 0 cannot stand alone, and 20 is valid, so dp[2] = dp[0] = 1. The next 2 adds dp[2] = 1, and 02 is not valid, so dp[3] = 1. The last 0 cannot stand alone, and 20 is valid, which adds dp[2] = 1, so dp[4] = 1. The only reading is 20 20, which gives TT.

Exercise 3. Explain why "30" has 0 ways, and why "10" has 1 way.

Show the answer

The 3 can stand alone, but the 0 cannot, so the pair 30 must be read together. The value 30 is above 26, so it is not valid, which leaves no way. For "10", the pair is 10, which is valid, and the two-character reading gives one way. The 1 cannot stand alone because the 0 would then be left by itself.

Exercise 4. A string of ten ones, "1111111111", has F(11) ways. What is that number, and how do you check it with the program?

Show the answer

F(11) is 89. The program in Step 5 gives 7540113804746346429 for ninety-one ones, which is F(92), so the pattern holds. Running count_ways("1" * 10) prints 89.

Exercise 5. Change count_ways so it returns 0 for an empty string instead of 1. Explain why the change is a decision about the problem, not a fix for a bug.

Show the answer

Add if s == "": return 0 at the top of the function. The empty string has one way under the convention that dp[0] = 1, which is the standard setup. Returning 0 says that empty input is not a valid code. Which answer is right depends on what the problem asks, so the choice must be written in the problem statement or in a comment.

Summary

• Decode ways is string partition DP with two piece lengths: a single digit from 1 to 9, and a two-digit value from 10 to 26.
• The table dp[i] adds dp[i - 1] when the last character is 1 to 9, and dp[i - 2] when the last two characters form a value from 10 to 26.
• The zero rules are the main source of bugs, so test strings with zeros in them.
• The table only reads two earlier cells, so two variables are enough.
• Counts grow like Fibonacci numbers, so Python's exact integers suit them, and a modulo is used when the problem asks for one.