1-D Dynamic Programming Take it or skip it
518. Decode Ways
Each capital letter can be written as a number: A is 1, B is 2, and so on up to Z, which is 26. A
message is turned into digits by writing the number of each letter, one after another, with nothing between
them. So "BAT" becomes "2120".
You are given a string of digits, s. Return how many different messages turn into exactly s.
No letter is written with a leading zero, so "05" is not E, and a 0 on its own is not a letter. If no
message turns into s, return 0. The count can be very large, so return it modulo 109 + 7.
Example 1
Input: s = "12120"
3Explanation: A 0 cannot stand alone, so the last two digits must be 20, which is T. The 121 before it is ABA,
LA or AU, so the three messages are ABAT, LAT and AUT.
Example 2
Input: s = "2101"
1Explanation: The 0 must pair with the 1 before it, as 10, which is J. That leaves the 2 and the last 1 on their
own, so the only message is BJA.
Example 3
Input: s = "111111111111111111111111111111111111111111111111111111111111"
730764433Explanation: Every letter here is A (1) or K (11). There are 2,504,730,781,961 messages, so the answer is that
count modulo 109 + 7.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds only the digits 0 to 9, and it may start with a 0
Clarifying questions
What you would ask an interviewer before writing any code.