Skip to main content

91. Decode Ways

mediumAsked at Google

Given a digit string, count the ways it can be decoded as letters (A=1...Z=26). Google asks this to test whether you reach for 1D DP and can handle the edge cases around '0' digits which can't stand alone.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L3/L4 onsite reports cite this as the DP warm-up.
  • Reddit r/cscareerquestions (2025-10)— Common Google new-grad interview question.

Problem

A message containing letters from A-Z can be encoded into numbers using the following 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 (there may be multiple ways). 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: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2

Input
s = "226"
Output
3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

Input
s = "06"
Output
0

Explanation: "06" cannot map to "F" because of the leading zero.

Approaches

1. Recursion with memoization

f(i) = ways to decode s[i..]. Try 1-digit and 2-digit splits if valid.

Time
O(n)
Space
O(n)
function numDecodingsMemo(s) {
  const memo = new Map();
  function solve(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo.has(i)) return memo.get(i);
    let res = solve(i + 1);
    if (i + 1 < s.length) {
      const two = Number(s[i] + s[i + 1]);
      if (two >= 10 && two <= 26) res += solve(i + 2);
    }
    memo.set(i, res);
    return res;
  }
  return solve(0);
}

Tradeoff: Recursive form makes the subproblem clear. Same complexity as bottom-up but uses recursion stack.

2. Bottom-up 1D DP (optimal)

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

Time
O(n)
Space
O(n) or O(1) with two-var trick
function numDecodings(s) {
  if (!s.length || s[0] === '0') return 0;
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    if (s[i - 1] !== '0') dp[i] += dp[i - 1];
    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

Tradeoff: Standard 1D DP. The two conditions — single-digit valid (not '0') and two-digit valid (10-26) — track the two ways to extend dp[i].

Google-specific tips

Google interviewers grade this on edge-case discipline. The '0' digit is the gotcha: '0' alone can never decode, but '10' and '20' are valid. State out loud: 'Single digits 1-9 work alone; single 0 fails; two-digit 10-26 works (including 10 and 20).' If you miss any of those, the test cases catch you.

Common mistakes

  • Treating '0' as a valid single digit (it's not — A starts at 1).
  • Allowing two-digit numbers like '07' (invalid — leading zero).
  • Off-by-one: dp[i] represents the prefix of length i, not the index i.

Follow-up questions

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

  • What if the message contains '*' which matches any digit 1-9 (LC 639)?
  • Return the actual decoded strings, not just the count.
  • What if you needed to decode in a specific way (e.g., maximize a property)?

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 this a DP problem?

Overlapping subproblems: f(i) depends only on f(i+1) and f(i+2). The recurrence has a fixed structure with no exponential branching once you memoize.

Can it be done in O(1) space?

Yes — at each step, dp[i] only depends on dp[i-1] and dp[i-2]. Keep two variables and roll forward.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →