Decode Ways
Problem
Letters are encoded as numbers: A = 1, …, Z = 26. Given a digit string, return how many ways it can be decoded. "06" is not a valid code, so a 0 can only appear as part of 10 or 20.
Example 1
Input: "12" Output: 2
"AB" (1, 2) or "L" (12).
Example 2
Input: "226" Output: 3
Example 3
Input: "06" Output: 0
Test cases
Case 1
Input: "12" Expected: 2
Case 2
Input: "226" Expected: 3
Case 3
Input: "06" Expected: 0
Case 4
Input: "10" Expected: 1
View solutionHide solution1 approach
1. Rolling DP over prefixes
Time O(n)Space O(1)
ways(i) takes ways(i − 1) if s[i−1] is 1–9, plus ways(i − 2) if s[i−2..i−1] is 10–26. A "0" can only be the second digit of 10 or 20.
function numDecodings(s) { let prev2 = 1, prev1 = s[0] === '0' ? 0 : 1; for (let i = 2; i <= s.length; i++) { let cur = 0; if (s[i - 1] !== '0') cur += prev1; const two = Number(s.slice(i - 2, i)); if (two >= 10 && two <= 26) cur += prev2; [prev2, prev1] = [prev1, cur]; } return prev1;}