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
is0
, there is no possible decoding. The problem statement specifies that leading zeros aren’t allowed. So1
decodes toA
, but01
doesn’t decode to anything. If the current digit is0
, this is an invalid position, and we’ll exit.If
d1 > 0
then we can decoded1
into a letter betweenA
(1) andI
(9), and move to the next character.In addition to the previous case, if
d1 > 0
andd1d2
represents a number between 10 and 26 (inclusive), we can decode the combined number into a letter betweenJ
(10) andZ
(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.