Skip to main content

68. Decode Ways

mediumAsked at Ola

Count the number of ways to decode a digit string into letters A-Z.

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

Problem

A message containing letters from A-Z is encoded as digits ('A'->'1', 'Z'->'26'). 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

Example 2

Input
s = "226"
Output
3

Approaches

1. Recursive

Try taking 1 digit or 2 digits at each step.

Time
O(2^n)
Space
O(n)
// raw recursion; exponential without memo

Tradeoff:

2. DP rolling two states

dp[i] = ways to decode s[0..i]; add dp[i-1] if s[i-1] != '0' and dp[i-2] if s[i-2..i-1] in 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 curr = 0;
    if (s[i] !== '0') curr += prev1;
    const two = +s.slice(i-1, i+1);
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff:

Ola-specific tips

Ola asks decode-ways to test classic 1D DP with edge cases (zeros); tie it to counting valid ways to parse a stream of compressed driver-status codes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →