Skip to main content

91. Decode Ways

medium

Count the number of ways to decode a string of digits into letters where 1->A through 26->Z. Edge cases around zeros make this trickier than Climbing Stairs even though the recurrence is similar.

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

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). For example, '11106' can be mapped into 'AAJF' with the grouping (1 1 10 6) or 'KJF' with the grouping (11 10 6). Note that the grouping (1 11 06) is invalid because '06' cannot be mapped into 'F' since '6' is different from '06'. 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 be mapped to "F" because of the leading zero ("6" is different from "06").

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i] = number of ways to decode s[0..i-1].

Hint 2

Single-digit decode is valid iff s[i-1] != '0'. Two-digit decode is valid iff s[i-2..i-1] forms 10..26.

Hint 3

Transitions: dp[i] += dp[i-1] if single-digit valid; dp[i] += dp[i-2] if two-digit valid.

Solution approach

Reveal approach

Bottom-up DP. dp[0] = 1 (empty string, one way: empty decoding). dp[1] = 1 if s[0] != '0' else 0. For i = 2..n: dp[i] starts at 0. If s[i-1] != '0', dp[i] += dp[i-1] (single-digit decode). If s[i-2..i-1] forms a number in [10, 26], dp[i] += dp[i-2] (two-digit decode). Return dp[n]. Edge case: if the string starts with '0', dp[1] = 0 forces all later dp values to 0 — correct since no valid decoding exists. O(n) time, O(n) space (reducible to O(1) with rolling variables).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • fibonacci

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Decode Ways and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →