29. Decode Ways

mediumAsked at Apple

Count all valid decodings of a digit string where 1-26 map to A-Z — Apple uses this DP pattern to evaluate how engineers reason about combinatorial text-parsing states, directly analogous to the multi-codepoint emoji rendering decisions in iMessage.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

A message containing letters A-Z can be encoded as numbers with 'A' -> '1', 'B' -> '2', ..., 'Z' -> '26'. Given a string s containing only digits, return the number of ways to decode it. If there are no valid decodings, return 0.

Constraints

1 <= s.length <= 100
s contains only digits
s may contain leading zeros

Examples

Example 1

Input

s = "12"

Output

Explanation: Decoded as 'AB' (1 2) or 'L' (12)

Example 2

Input

s = "226"

Output

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

Example 3

Input

s = "06"

Output

Explanation: '06' is not valid — leading zero has no mapping

Approaches

1. Recursive with memoization

Recurse from position i: try single-digit decode (if non-zero) and two-digit decode (if 10-26). Memoize by index.

Time: O(n)
Space: O(n)

function numDecodings(s) {
  const memo = new Map();
  const dp = (i) => {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo.has(i)) return memo.get(i);
    let ways = dp(i + 1);
    if (i + 1 < s.length) {
      const two = parseInt(s.slice(i, i + 2));
      if (two >= 10 && two <= 26) ways += dp(i + 2);
    }
    memo.set(i, ways);
    return ways;
  };
  return dp(0);
}

Tradeoff:

2. Bottom-up DP (space-optimized)

Build dp array left-to-right. dp[i] = ways to decode s[0..i-1]. Only need previous two values, so reduce to O(1) space.

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 = parseInt(s.slice(i - 1, i + 1));
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff:

Apple-specific tips

Apple's iMessage team deals with UTF-8 multi-byte sequences and emoji ZWJ sequences — the codepoint-boundary decision at each position is structurally identical to this decode-ways problem. The '06' edge case (leading zero inside the string, not just at start) catches most candidates; Apple interviewers insert it specifically to test boundary rigor. Narrate your dp[i] meaning explicitly — 'dp[i] is the number of ways to decode the first i characters' — Apple grades on communication as heavily as correctness.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →