Decode Ways

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}