Decode Ways
Medium1-D dynamic programming
A message of capital letters was turned into digits with A = 1, B = 2, and so on up to Z = 26, and the digits were written down with nothing between them.
Given the digits s, return how many different letter messages could have produced them. A group of digits is a letter only if it is a number from 1 to 26 with no leading zero, so "05" is not a letter. If no message fits, return 0.
Examples
Input: s = "13" Output: 2
AC (1, 3) or M (13).
Input: s = "2611" Output: 4
2 6 1 1, 26 1 1, 2 6 11 and 26 11. 61 is too big to be a letter.
Constraints
1 ≤ s.length ≤ 100sholds digits only, and may start with a 0.
Stuck?
Hint 1
The last letter used either one digit or two. So the ways to read the first i digits are the ways for i - 1 (if digit i alone is a letter) plus the ways for i - 2 (if the last two digits make a letter).
Hint 2
A lone 0 is never a letter, and a two-digit group must be between 10 and 26. Keep the last two counts and walk along the string.
The idea
The last letter of a message used either the final digit alone or the final two digits. So the readings of the first i digits are the readings of the first i - 1, if the final digit is a letter, plus the readings of the first i - 2, if the final two digits are a letter. Walk along the string keeping only those two counts.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
twoBack starts as the count for no digits at all: one way to read nothing, which lets a valid first pair count as a reading. oneBack is the count for the first digit, which is a letter unless it is 0.
function numDecodings(s) { let twoBack = 1; let oneBack = s[0] === '0' ? 0 : 1; for (let i = 2; i <= s.length; i++) { let ways = 0; if (s[i - 1] !== '0') ways += oneBack; const pair = Number(s.slice(i - 2, i)); if (pair >= 10 && pair <= 26) ways += twoBack; twoBack = oneBack; oneBack = ways; } return oneBack;}The trap
Checking only that a pair is at most 26 looks like the whole rule, since 26 is the last letter. But a pair that starts with 0 turns into a number below 10, passes that check, and is counted as a letter it can never be. Any string where a 0 is followed by another digit gets readings that do not exist.
function numDecodings(s) { let twoBack = 1; let oneBack = s[0] === '0' ? 0 : 1; for (let i = 2; i <= s.length; i++) { let ways = 0; if (s[i - 1] !== '0') ways += oneBack; if (Number(s.slice(i - 2, i)) <= 26) ways += twoBack; // lets "01" through twoBack = oneBack; oneBack = ways; } return oneBack;}