62. Decode Ways

Q: Why is '0' tricky?

'0' has no single-digit decode. It only contributes via two-digit codes (10 or 20). All other digits have a single-digit decode.

Q: Why initialize prev2 = prev1 = 1?

prev2 represents 'ways to decode empty prefix' (1, by convention). prev1 represents 'ways to decode first character' (1, since first char was checked to not be '0').

mediumAsked at Salesforce

Count the number of ways to decode a string of digits (1-26 → A-Z). Salesforce uses this to test DP with conditional transitions.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

Glassdoor (2026-Q1)— Salesforce uses similar DP for parsing structured fields.
LeetCode Discuss (2025-10)— Tests careful base cases (leading zero).

Problem

A message containing letters from A-Z can be encoded into numbers using the following 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 zero(s).

Examples

Example 1

Input

s = "12"

Output

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

Example 2

Input

s = "226"

Output

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

Example 3

Input

s = "06"

Output

Explanation: 06 is not a valid mapping.

Approaches

1. Recursive without memo

decode(i) = decode(i+1) + decode(i+2 if 2-digit is 10-26).

Time: O(2^n)
Space: O(n)

function numDecodings(s) {
  function dec(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    let count = dec(i + 1);
    if (i + 1 < s.length && parseInt(s.slice(i, i + 2)) <= 26) count += dec(i + 2);
    return count;
  }
  return dec(0);
}

Tradeoff: Exponential. Salesforce will dock for not memoizing.

2. Iterative DP with O(1) space

dp[i] = ways to decode s[0..i]. dp[i] = dp[i-1] if s[i] != '0', plus dp[i-2] if s[i-1..i] is 10-26.

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

Tradeoff: O(1) space rolling DP. The conditional transitions (single digit non-zero, two-digit 10-26) are the key signals.

Salesforce-specific tips

Salesforce specifically tests the boundary cases: leading zero, '06' (invalid two-digit), '10' (only valid as 10, not 1+0). They grade on whether you handle '0' explicitly. Bonus signal: mention this generalizes to k-character lookbacks for k-digit codes — same DP shape.

Common mistakes

Forgetting that '0' alone is invalid — must be paired with 1 or 2 from prior digit.
Treating '20' as 2+0 — '0' isn't a valid single decode.
Off-by-one in slice (slice(i-1, i+1) for two digits ending at i).

Follow-up questions

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

Decode Ways II (LC 639) — with wildcards.
Reconstruct ALL decodings.
What if the mapping range is 1-99?

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 '0' tricky?

'0' has no single-digit decode. It only contributes via two-digit codes (10 or 20). All other digits have a single-digit decode.

Why initialize prev2 = prev1 = 1?

prev2 represents 'ways to decode empty prefix' (1, by convention). prev1 represents 'ways to decode first character' (1, since first char was checked to not be '0').

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →