Skip to main content

68. Decode Ways

mediumAsked at Snowflake

Count the number of ways to decode a digit string into letters (A=1, B=2, ..., Z=26). Snowflake asks this for 1D DP with branching transitions — relevant to ambiguous tokenization during SQL parsing.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up ambiguous-grammar discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad screens.

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A'->'1', ..., '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

Example 3

Input
s = "06"
Output
0

Approaches

1. Recursive without memo

decode(i) = decode(i+1) [single digit, if valid] + decode(i+2) [pair, if valid].

Time
O(2^n)
Space
O(n)
// outline only — exponential.

Tradeoff: Exponential. Mention to reject.

2. 1D DP (optimal)

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

Time
O(n)
Space
O(1) with rolling vars
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.slice(i - 1, i + 1), 10);
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: Linear, rolling-variable DP. The 'two transitions' shape generalizes to any ambiguous-tokenization problem.

Snowflake-specific tips

Snowflake interviewers want the two-transition DP and explicit handling of edge cases (leading 0, '10' / '20' which have only one decode, etc.). Bonus signal: discuss ambiguous tokenization — when the SQL parser encounters tokens like '0.5' it must decide between literal float and an integer followed by '.5', similar to the choice between single-digit and double-digit decoding here.

Common mistakes

  • Forgetting to handle leading 0 — returns 1 instead of 0.
  • Treating '06' as a valid pair (it's 06, not 6 — must be 10..26).
  • Off-by-one between dp[i] (ways for s[:i]) and s[i-1] (current char).

Follow-up questions

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

  • Decode Ways II (LC 639) — with wildcard '*'.
  • Count substrings that are valid decodings.
  • How does Snowflake's SQL parser disambiguate tokens?

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 are 10 and 20 special?

Their only decoding is the two-digit version (10 = J, 20 = T). The single-digit 0 isn't a letter, so dp[i-1] contribution is 0.

How does this connect to SQL tokenization?

When the parser sees '12345.6', it must choose between treating '12345' as integer then '.6' as float continuation, or '12345.6' as one float literal. Snowflake's tokenizer uses greedy-longest-match with similar two-transition logic.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →