Skip to main content

60. Decode Ways

mediumAsked at Datadog

Count the number of ways to decode a digit string into letters (A=1, B=2, ..., Z=26). Datadog asks this for the 1D DP pattern — same shape as their dynamic-parser that branches on ambiguous log-line prefixes.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite DP question.

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 test cases are generated so that the answer fits 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
2

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

Example 2

Input
s = "226"
Output
3

Explanation: "BZ", "VF", "BBF".

Example 3

Input
s = "06"
Output
0

Explanation: Leading zero is invalid.

Approaches

1. Recursive without memo

f(i) = ways to decode s[i..]. Branch on take-1-digit and take-2-digit.

Time
O(2^n)
Space
O(n)
function numDecodings(s) {
  function f(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    let total = f(i + 1);
    if (i + 1 < s.length && parseInt(s.substring(i, i + 2), 10) <= 26) total += f(i + 2);
    return total;
  }
  return f(0);
}

Tradeoff: Exponential without memo.

2. 1D DP with two-state rolling (optimal)

dp[i] = ways for s[0..i-1]. dp[i] = (take 1 valid ? dp[i-1] : 0) + (take 2 valid ? dp[i-2] : 0).

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 curr = 0;
    if (s[i] !== '0') curr += prev1;
    const two = parseInt(s.substring(i - 1, i + 1), 10);
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(1) space, single pass. Datadog-canonical: rolling-2-state DP is the same shape as their ambiguous-prefix parser.

Datadog-specific tips

Datadog grades on the edge cases: leading 0, '0' in the middle, '10' and '20' (two-digit only), and '30+' first digit (one-digit only). Articulate all four cases before coding.

Common mistakes

  • Forgetting the s[0] === '0' early return.
  • Treating '06' as a valid two-digit decode — it's not; leading zeros invalidate.
  • Counting '0' on its own as 0 ways without realizing — '0' has no decoding.

Follow-up questions

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

  • Decode Ways II (LC 639) — with wildcard '*'.
  • Climbing Stairs (LC 70) — similar recurrence, no validity check.
  • Datadog-style: count valid parsings of an ambiguous log-line prefix.

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 'two >= 10' check?

two = '0X' would be invalid (leading zero). >= 10 excludes such cases.

What if the string is empty?

Conventionally 1 way (decode the empty string as the empty message). The problem says length >= 1, so we don't worry about it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →