LeetCode 91: Decode Ways

Last week, we looked at a dynamic programming counting problem, Climbing Stairs. This week’s problem, LeetCode 91: Decode Ways, is also a counting problem. And although the problems may not seem very similar on the surface, we can adapt the Climbing Stairs solution to solve Decode Ways.

The input to the Decode Ways problem is a string where each character is a digit. This string of digits represents a message encoded using a simple 1-based mapping of letters to numbers: A maps to 1, B maps to 2, and so on through Z and 26. However, since there are no delimiters in the encoded message, there may be more than one way to decode a message. Our job is to return the number of ways that the input message can be decoded.

We can solve this problem using two key ideas:

Key Idea 1: Enumerate Cases

At each position in the string, we have zero, one, or two options for decoding. If d1 is the current digit and d2 is the next digit, then:

• If d1 is 0, there is no possible decoding. The problem statement specifies that leading zeros aren’t allowed. So 1 decodes to A, but 01 doesn’t decode to anything. If the current digit is 0, this is an invalid position, and we’ll exit.

• If d1 > 0 then we can decode d1 into a letter between A (1) and I (9), and move to the next character.

• In addition to the previous case, if d1 > 0 and d1d2 represents a number between 10 and 26 (inclusive), we can decode the combined number into a letter between J (10) and Z (26), and move ahead two positions.

Key Idea 2: Climbing Stairs

In the previous enumeration, if d1 > 0, we have two options: 1) Decode the next digit into a single letter, or 2) Decode the next two digits into a single letter (if the two digits form a number in the appropriate range). If both cases apply at a position, our counting process splits into two paths: the path where we use a single digit, and the path where we use two digits.

This is where the solution starts to look similar to Climbing Stairs. In that problem, we could take either one or two steps from each position on the staircase. And we always have those two options. When we’re decoding the string, there are three options: decode zero, one, or two digits. Once we know which of those options applies, the rest of the implementation is just like Climbing Stairs.

Memoization

As usual, dp[i] represents the solution starting at position i. So dp[0] will be the number of ways to decode the entire string.

Pseudocode

Look at the Climbing Stairs pseudocode to see how it compares with this solution.

input: string s
define an int array dp of the same length as s
return count(0, s)

int count(int i, string s)
    // decoding is complete
    if i is past the last character of s
        return 1

    d1 = digit at position i

    // invalid decoding; leading 0's are not allowed
    if d1 is 0
        return 0

    // only the single-digit decoding is possible here
    if i is at the last character of s
        return 1

    // check the memo table
    if dp[i] > 0
        return dp[i]

    // make the 2-digit number d1d2
    d2 = digit at position i+1
    num = d1*10+d2

    // count the number of ways if we only decode one character
    c = count(i+1, s)

    // if applicable, count the number of ways if we decode two characters
    if num <= 26
        c += count(i+2, s)

    // update memo table
    dp[i] = c

    return c

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.