Decode Ways

Difficulty: Medium

Problem

A message made of capital letters was turned into digits using A→1, B→2, ... Z→26. Given only the resulting digit string, count the number of distinct letter messages it could have come from. For example "12" may be read as "AB" (1|2) or "L" (12), giving two ways. The recurrence resembles Climbing Stairs, but zeros and the 26 cap create plenty of tricky edge cases.

Example

Input: s = "1123"
Output: 5
Explanation: The splits are 1|1|2|3 (AABC), 11|2|3 (KBC), 1|1|23 (AAW), 11|23 (KW) and 1|12|3 (ALC), for five decodings in total.

Brute-force approach

The naive recursion is taught inside the guided walkthrough: the branches explode exactly like Climbing Stairs.

Optimal approach

Key insight: The last letter of any decoding covers 1 or 2 digits, Climbing Stairs' split, but each branch must pass a legality check before its ways are counted.

One left-to-right pass: each position sums the 1-digit branch (if the digit isn't 0) and the 2-digit branch (if the pair is 10..26).

Steps

  1. Guard: a leading '0' → return 0
  2. Bases: dp[0] = 1 (empty), dp[1] = 1
  3. dp[i] = (s[i−1] ≠ '0' ? dp[i−1] : 0) + (10 ≤ s[i−2..i−1] ≤ 26 ? dp[i−2] : 0)
  4. Answer dp[n]; roll to two variables

Time complexity: O(n) · Space complexity: O(1) with rolling variables

Pseudocode

function numDecodings(s):
    if s[0] == ____:
        return 0
    prev2 = 1, prev1 = 1
    
    for i in 2 .. length(s):
        cur = 0
        if s[i-1] != '0':
            cur = cur + ____
        if ____ <= value(s[i-2..i-1]) <= ____:
            cur = cur + prev2
        prev2 = prev1
        prev1 = cur
    
    return prev1

Hints

  • Which leading character makes the whole string undecodable?
  • A legal single digit extends every decoding of the prefix one shorter
  • The two-digit window for letters J through Z is which range?
  • Failed guards simply add nothing, cur keeps whatever passed

Complexity questions

What is the time complexity?

O(n): one pass, constant work per position. The DP visits each position once with two guarded additions. The 2ⁿ lives only in the naive version's call tree.

Why is O(1) space available?

The transition reaches back exactly 2: the same rolling-variable audit as Climbing Stairs. dp[i] reads dp[i−1] and dp[i−2] only. Two variables carry the whole computation.

"100" has how many decodings, and why?

0: the first 0 pairs into '10', but the SECOND 0 has nothing to attach to: '00' is illegal and '0' alone is illegal. dp walk: '1'→1, '10'→ single 0 fails, pair 10 ✓ → 1 way; third char '0': single fails, pair '00' fails → 0. Zeros must each find a 1 or 2 to their left.

Which earlier problems share this exact two-backward-reach skeleton?

Climbing Stairs and Min Cost Climbing Stairs. Count/min/count-with-guards are one family with different combiners and guards. Stairs summed freely; Min Cost minned with tolls; Decode Ways sums with legality guards. Recognizing the family means you start from the transition, not from scratch.

Check your understanding of Decode Ways

What are the legal 'chunks' a decoding is built from?

A 1-digit chunk '1'..'9', or a 2-digit chunk '10'..'26' — '0' alone and '27'+ decode to nothing. Letters are 1..26. So a single '0' is illegal (no letter is 0), and two-digit chunks work only for 10..26. Every wrong answer on this problem traces back to forgetting one of these.

Why is this 'Climbing Stairs with guards'?

The last chunk covers 1 or 2 digits, the same two backward reaches, but each reach is only counted if its chunk is LEGAL. dp[i] = (1-digit chunk legal ? dp[i−1] : 0) + (2-digit chunk legal ? dp[i−2] : 0). Same skeleton, with an if in front of each branch.

What does a '0' in the string force?

The 0 MUST be the second digit of '10' or '20'. Otherwise the whole string has zero decodings. '0' alone decodes to nothing, and '30', '40'... exceed no letter... rather: 30+ isn't ≤26 and doesn't end in a valid pair either. Only '10' and '20' can absorb a 0. "06" → 0 ways; "106" → 1 way (10|6).

Trace "226": why exactly 3?

dp: base 1,1 → dp[2] = dp[1] + dp[0] = 2 ('2|2' and '22') → dp[3] = dp[2] + dp[1] = 3 ('...6' single, and '26' double). Both branches are legal at every step here: '2','2','6' all valid singles, '22' and '26' valid doubles. The Fibonacci pattern appears whenever no guard fires.

What are the base cases?

dp[0] = 1 (the empty string decodes ONE way: say nothing) and dp[1] = 1 if s[0] ≠ '0' else the answer is 0. dp[0] = 1 puzzles people: it's the multiplicative identity, the 2-digit chunk covering the whole first pair inherits from 'nothing before it', which must count as one way, not zero. And a leading '0' kills everything immediately.

Related problems

Keep practising