91. Decode Ways

Letters map to numbers: 'A' → 1 … 'Z' → 26. Return how many ways a digit string s can be decoded back into letters.

The bottom-up recurrence only looks two steps back, so keep two counters.

1function numDecodings(s: string): number {
2  let prev2 = 1, prev1 = s[0] === "0" ? 0 : 1;
3  for (let i = 2; i <= s.length; i++) {
4    let cur = s[i - 1] !== "0" ? prev1 : 0;
5    const two = Number(s.slice(i - 2, i));
6    if (two >= 10 && two <= 26) cur += prev2;
7    [prev2, prev1] = [prev1, cur];
8  }
9  return prev1;
10}

prev2 = 1prev1 = 1

s

prev2 = 1, prev1 = 1.

1 / 0

Space: play/pause · ←/→: step