Overview

A message containing letters A-Z can be encoded as numbers using the mapping: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".

Given a string s containing only digits, return the number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer.

Constraints

• 1 <= s.length <= 100
• s contains only digits and may contain leading zeros.
• A leading zero (like "06") is not a valid encoding.

Examples

numDecodings("12");
// => 2  ("AB" or "L")

numDecodings("226");
// => 3  ("BZ", "VF", "BBF")

numDecodings("06");
// => 0  (leading zero — no valid decoding)

Solution

function numDecodings(s) {
  if (s[0] === "0") return 0;
  const n = s.length;
  let prev2 = 1, prev1 = 1;

  for (let i = 1; i < n; i++) {
    let curr = 0;
    if (s[i] !== "0") curr += prev1;
    const two = parseInt(s.substring(i - 1, i + 1));
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

Resources

• Decode Ways — LeetCode
• Dynamic Programming — Wikipedia