Skip to main content

63. Decode Ways

mediumAsked at Reddit

Count the number of ways to decode a digit string to letters (A=1..Z=26). Reddit uses this DP problem to test recurrence design — the same shape used in their tokenizer when a sequence of input bytes has multiple valid prefix interpretations.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, DP medium.

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 using the reverse of the mapping above. Given a string s containing only digits, return the number of ways to decode it.

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

Explanation: "BBF" (2 2 6), "BZ" (2 26), "VF" (22 6).

Example 3

Input
s = "06"
Output
0

Explanation: Leading zero — invalid.

Approaches

1. Recursion no memo

dp(i) = dp(i+1) (single digit) + dp(i+2) (two digits) when valid.

Time
O(2^n)
Space
O(n)
// Anti-pattern: exponential branching without memo.

Tradeoff: TLE for n > 20.

2. Iterative DP with O(1) space (optimal)

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

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

Tradeoff: Linear time, constant space. The dual valid-single + valid-double check is the recurrence.

Reddit-specific tips

Reddit interviewers care that you handle '0' carefully. Bonus signal: enumerate the edge cases up front — leading 0, standalone 0 (invalid), valid pairs (10-26). State the recurrence verbally first.

Common mistakes

  • Treating '0' as a valid standalone (it's not).
  • Allowing two-digit codes like '06' or '00' (only 10-26 are valid).
  • Forgetting the s[0] === '0' early-return.

Follow-up questions

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

  • Decode Ways II (LC 639) — with '*' wildcards.
  • Word break (LC 139) — same DP shape, dictionary lookup.
  • Longest valid parentheses (LC 32).

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 prev2 = 1 initially?

Empty prefix has one decoding (the empty string). prev1 = 1 corresponds to the first char which we just validated as non-zero.

What about leading-zero edge case?

Return 0 immediately. Also handle two-digit codes '00', '01'..'09' as invalid as a two-digit chunk.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →