Decode Ways — Dynamic Programming
Today we are looking at the dynamic programming problem decode ways.
If you haven’t ever seen the problem climbing stairs, I suggest checking it out first. It is an easier dynamic programming problem and helps build into this problem.
Alright, so the question is asking us how “many ways” we can decode a number into different letter combinations. In climbing stairs we needed to find how many ways we could climb to the top using 1 or 2 stairs at a time. We solved this by looking at how many previous ways we had climbed to the top using one stair PLUS how many ways we had climbed to the top using two stairs. Our problem is just a slight variation of this. In this problem numbers can be decoded into letters, the trick here is that only the numbers 1–26 matter. They are the only numbers that match up with a letter. Here we need to check each digit individually and check it as a pair with the previous number. Then we will add together how many ways we have previously made single digit numbers PLUS how many ways we have made two digit numbers. Alright let’s dive into the code.
First we need to initialize our array. We will make our array a length of n + 1 because index 0 of our array will represent an empty string (‘’). We will set our dp[0] = 1. This represents how many ways we can make an empty string. Then we will loop through each digit in our number. We will need to check if each digit/digits corresponds to a letter. We will have two options, one represents a single digit and the other represents a two digit number. If the first option is greater than zero then we set our dp[i] = dp]i-1]. We know there is one way to make a single a digit number, so we want to set our dp[i] equal to how many previous ways we could make a single digit number. Then we check our second option. If this number is greater than 10 and less than 26 then we know it represents a letter and we want to know how many previous ways we had made two digit letters PLUS how many ways we had made one digit letters. This will be dp[i] += dp[i-2]. Like in climbing stairs we look either one stair behind or two stairs behind, here we look at one digit individually and then the current digit and the previous digit together. So we can think of it as taking 1 stair or 2 stairs, but it is either one digit letter or two digit letter. Our conditional for the single digit is greater than zero because if our number is a zero we want to skip it. A zero indicates there is no possible way to decode (I’ll show in an example below). Then our second conditional is greater than 10 and less than 26. Obviously the 26 makes sense, since this is the length of the alphabet. The greater than 10 takes into account a two digit number that has a zero in the first position (Ex. 101).
Here is a couple example inputs:
