Decode Ways

The problem. Letters are encoded as numbers: A = 1, B = 2, …, Z = 26. Given a string of digits s, return the number of ways to decode it. A piece like 06 is not valid — no letter is encoded with a leading zero.

Example

s = "12"   ->  2   ("AB" from 1 2, "L" from 12)
s = "226"  ->  3   ("BZ", "VF", "BBF")
s = "06"   ->  0   (a leading zero can't be decoded)

The idea: the last letter used one or two digits

Let ways[i] be the number of decodings of the first i digits. The last letter of a decoding used either one digit — valid if s[i−1] isn't 0 — leaving ways[i−1] decodings for the rest, or two digits — valid if s[i−2..i−1] is between 10 and 26 — leaving ways[i−2]. Add the valid cases. ways[0] = 1: the empty string has one (empty) decoding. Zeros are the whole difficulty: 0 can only appear as part of 10 or 20.

1. Recursion with memoization

1function numDecodings(s) {2  const memo = new Map();3  const count = (i) => {                         // decodings of s[i..]4    if (i === s.length) return 1;                // nothing left: one way5    if (s[i] === "0") return 0;                  // no letter starts with 06    if (memo.has(i)) return memo.get(i);7    let total = count(i + 1);                    // one digit8    if (i + 1 < s.length && Number(s.slice(i, i + 2)) <= 26) total += count(i + 2);   // two digits9    memo.set(i, total);10    return total;11  };12  return count(0);13}

Time O(n), space O(n). This version reads the string forwards from i, so its table would fill right to left — either direction works.

2. A table over prefixes

1function numDecodings(s) {2  const n = s.length;3  const ways = new Array(n + 1).fill(0);         // ways[i]: decodings of the first i digits4  ways[0] = 1;                                   // the empty prefix5  for (let i = 1; i <= n; i++) {6    if (s[i - 1] !== "0") ways[i] += ways[i - 1];             // last letter: one digit, 1-97    const two = i >= 2 ? Number(s.slice(i - 2, i)) : 0;8    if (two >= 10 && two <= 26) ways[i] += ways[i - 2];       // last letter: two digits, 10-269  }10  return ways[n];11}

Time O(n), space O(n) — or O(1) with two variables, exactly as in Climbing Stairs (which this is, with rules about which steps are allowed).

Comparing the approaches

Edge cases to test

Variations