Skip to main content

64. Decode Ways

mediumAsked at Vercel

Count the number of ways to decode a numeric string into letters (1=A, 2=B, ..., 26=Z). Vercel asks this for the 1D DP with conditional transitions — same shape as counting valid parses of compressed config strings.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; DP expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

A message containing letters from A-Z can be encoded into numbers using the mapping A->1, B->2, ..., Z->26. To decode an encoded message, all the digits must be grouped then mapped back into letters. Given a string s containing only digits, return the number of ways to decode it. The test cases are generated so that the answer fits in a 32-bit integer.

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Examples

Example 1

Input
s = "12"
Output
2

Explanation: AB (1, 2) or L (12).

Example 2

Input
s = "226"
Output
3

Example 3

Input
s = "06"
Output
0

Explanation: Leading zero is invalid.

Approaches

1. Recursive top-down with memo

decode(i) = decode(i+1) if s[i] valid single + decode(i+2) if s[i..i+1] valid double.

Time
O(n)
Space
O(n)
function numDecodings(s) {
  const memo = new Array(s.length).fill(-1);
  function go(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo[i] !== -1) return memo[i];
    let count = go(i + 1);
    if (i + 1 < s.length && parseInt(s.substring(i, i + 2)) <= 26) count += go(i + 2);
    return memo[i] = count;
  }
  return go(0);
}

Tradeoff: Works. Iterative is preferred.

2. Iterative DP with rolling variables (optimal)

dp[i] = dp[i-1] (if s[i] valid single) + dp[i-2] (if s[i-1..i] valid double). Roll to two scalars.

Time
O(n)
Space
O(1)
function numDecodings(s) {
  if (s[0] === '0') return 0;
  let prev2 = 1, prev1 = 1;
  for (let i = 1; i < s.length; i++) {
    let cur = 0;
    if (s[i] !== '0') cur += prev1;
    const two = parseInt(s.substring(i - 1, i + 1));
    if (two >= 10 && two <= 26) cur += prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Tradeoff: O(1) extra space. The two conditions (single is valid iff not zero; double is valid iff 10-26) handle the leading-zero edge case naturally.

Vercel-specific tips

Vercel grades the rolling-variable DP. Bonus signal: explicit handling of '0' (any standalone 0 zeros the count) and the 10-26 range for doubles (not 0-26 — leading-zero doubles like '06' are invalid).

Common mistakes

  • Allowing '06' as a valid double — it's not.
  • Forgetting to handle the leading zero case (`if (s[0] === '0') return 0`).
  • Off-by-one in the substring bounds — i-1 to i+1 means characters at indices i-1 and i.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Decode Ways II (LC 639) — '*' wildcards for any digit.
  • Construct one valid decoding.
  • Generate ALL decodings — backtracking instead of counting.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the double range 10-26 and not 0-26?

A double '06' has a leading zero, which is not a valid encoding (no letter maps to '06'). The range must start at 10.

Why does s[0] === '0' return 0?

Because any single starting with 0 is invalid, AND there's no character before it to form a double. So no valid decoding exists.

Practice these live with InterviewChamp.AI

Drill Decode Ways and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →