Skip to main content

22. Decode Ways

mediumAsked at Adobe

Count the number of ways to decode a numeric string where '1'-'26' map to 'A'-'Z'. Adobe tests this problem to assess DP string-parsing skills and careful handling of edge cases like leading zeros — patterns central to font encoding, barcode parsing, and document format decoding in Creative Cloud.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • LeetCode Discuss (2025-10)— Adobe candidates report string DP problems including decode ways in SDE-II phone screens.
  • Glassdoor (2026-01)— Adobe interviewers use string parsing DP problems to test edge-case awareness.

Problem

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

Constraints

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

Examples

Example 1

Input
s = "12"
Output
2

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

Example 2

Input
s = "226"
Output
3

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

Example 3

Input
s = "06"
Output
0

Explanation: '06' cannot be decoded — '0' has no mapping.

Approaches

1. Recursive with memoization (top-down)

Recursively try 1-digit and 2-digit decodings from the current index, memoize by index.

Time
O(n)
Space
O(n)
function numDecodings(s) {
  const memo = new Map();
  function 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: Correct and O(n); Adobe will ask for the bottom-up version to demonstrate DP fluency.

2. Bottom-up DP with O(1) space

Define dp[i] as the number of ways to decode s[i..n-1]. Iterate right to left. At each position, try 1-digit decode (if s[i] != '0') and 2-digit decode (if s[i..i+1] in [10..26]). Only dp[i+1] and dp[i+2] are needed, so use two variables.

Time
O(n)
Space
O(1)
function numDecodings(s) {
  const n = s.length;
  let next2 = 1;  // dp[n] = 1 (empty suffix)
  let next1 = s[n - 1] !== '0' ? 1 : 0;  // dp[n-1]
  for (let i = n - 2; i >= 0; i--) {
    let ways = 0;
    if (s[i] !== '0') ways += next1;
    const two = parseInt(s.slice(i, i + 2));
    if (two >= 10 && two <= 26) ways += next2;
    next2 = next1;
    next1 = ways;
  }
  return n === 1 ? (s[0] !== '0' ? 1 : 0) : next1;
}

Tradeoff: O(n) time, O(1) space using the rolling-variable technique. The Adobe signal: correct handling of '0' as a digit (it can only be part of 10 or 20, never a standalone character).

Adobe-specific tips

Adobe interviewers pay close attention to how candidates handle the zero character — '0' alone is invalid, but '10' and '20' are valid. Write out the edge cases explicitly before coding: s='0', s='10', s='100', s='01'. This methodical approach reflects the defensive programming culture Adobe values in document-format parsers.

Common mistakes

  • Treating '0' as a valid single-digit decode — '0' has no mapping and should return 0 for that branch.
  • Checking two-digit decode for range [1..26] instead of [10..26] — '01' through '09' are not valid two-character encodings.
  • Off-by-one in the base case — dp[n] should be 1 (empty string = one way to decode: do nothing).

Follow-up questions

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

  • Decode Ways II (LC 639): '*' wildcard can represent any digit 1-9.
  • How would you reconstruct one valid decoding, not just count them?
  • How does this change if the encoding maps letters to multi-digit codes of variable length?

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 dp[n] = 1 (base case for empty suffix)?

An empty string has exactly one decoding: the empty decoding. This base case propagates correctly — if a single character is valid, it contributes dp[n]=1 to dp[n-1].

Can I use a left-to-right DP instead of right-to-left?

Yes — define dp[i] as ways to decode s[0..i-1]. dp[i] = dp[i-1] if s[i-1] != '0', plus dp[i-2] if s[i-2..i-1] is in [10..26]. Both directions work; right-to-left mirrors the recursive top-down formulation more naturally.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →