Decode Ways
Medium · 1-D Dynamic Programming
You are given a string of digits that represents a message encoded by mapping the letters A through Z to the numbers 1 through 26. Determine how many different ways the string could have originally been decoded back into letters. A decoding splits the string into consecutive blocks of one or two digits, each block being a value from 1 to 26, and no block may start with the digit 0. Return the total count of distinct valid decodings.
Examples
Input: s = "12"
Output: 2
Why: It can be split as 1-2 or as 12, mapping to letters AB or L, giving two valid decodings.Input: s = "226"
Output: 3
Why: Valid splits are 2-2-6, 22-6, and 2-26, giving three ways.Input: s = "06"
Output: 0
Why: A digit block cannot start with 0, so this string cannot be decoded at all.Constraints
1 <= s.length <= 100, s consists only of digits and may contain leading zeros
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Decode Ways. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.