Decode ways (recursion)

Medium TimeO(2ⁿ) naive; O(n) memoised SpaceO(n) stack

The letters A to Z were written as the numbers 1 to 26 and run together with no separators, so "12" could be "AB" or "L". Given such a string, return how many messages it could decode to. Only 1 to 26 are valid codes, so a leading 0 decodes to nothing, a two-digit code must read between 10 and 26, and a string that cannot be decoded at all answers 0.

Examples

Example 1

Input
s = '226'i = 0
Output
3
2 2 6, 22 6 and 2 26 — three readings; 226 itself is past 26.

Example 2

Input
s = '06'i = 0
Output
0
0 is not a code on its own and 06 reads below 10, so nothing decodes at all.

The Code

function decode(s, i) {
  if (i === s.length) return 1;
  if (s[i] === '0') return 0;
  let ways = decode(s, i + 1);
  if (i + 1 < s.length && parseInt(s.slice(i, i + 2), 10) <= 26) {
    ways += decode(s, i + 2);
  }
  return ways;
}
decode('226', 0);
Done
Step through decode('226', 0) call by call

More like this

All dynamic programming examples (20) →