Letters A to Z are encoded as the numbers 1 to 26. Given a string of digits, count the number of ways to decode it.
DSA Animator › DSA Revision › Dynamic Programming › Decode Ways
Remember: one digit or two digits, just like one step or two. A 0 can only be used as part of 10 or 20. The video solves Decode Ways (LeetCode 91, Medium) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Decode Ways animation.
Letters A to Z are encoded as the numbers 1 to 26. Given a string of digits, count the number of ways to decode it.
For 226, there are 3 ways. They are 2 2 6, which is B B F, then 22 6, which is V F, then 2 26, which is B Z.
Trying every way to split the string recursively repeats the same suffixes many times. Like climbing stairs, each position can be reached by one digit or by two.
Let dp of i be the number of ways to decode the first i characters. The empty prefix has exactly 1 way, so dp of 0 is 1. If the single digit at position i is not 0, add dp of i minus 1. If the last two digits form a number from 10 to 26, add dp of i minus 2. Zeros are the tricky part, because 0 alone is not a letter.
dp of 0 is 1. The first digit 2 is valid alone, so dp of 1 is 1. The next 2 is valid alone, and 22 is also valid, so dp of 2 is 1 plus 1, which is 2. The digit 6 is valid alone, adding 2. And 26 is valid, adding dp of 1, which is 1. So dp of 3 is 3.
In code, create dp of size n plus 1, with dp of 0 equal to 1. For each i, add dp of i minus 1 if the current digit is not 0. Add dp of i minus 2 if the two digit number is between 10 and 26. Return dp of n, so it's O of n time, or O of 1 space with two variables.
Remember: one digit or two digits, just like one step or two. A 0 can only be used as part of 10 or 20.