62. Decode Ways
mediumAsked at SalesforceCount the number of ways to decode a string of digits (1-26 → A-Z). Salesforce uses this to test DP with conditional transitions.
By Sam K., Founder, InterviewChamp.AI · Last verified
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 <= 100s contains only digits and may contain leading zero(s).
Examples
Example 1
s = "12"2Explanation: AB (1 2) or L (12).
Example 2
s = "226"3Explanation: BZ (2 26), VF (22 6), or BBF (2 2 6).
Example 3
s = "06"0Explanation: 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.
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').