Decode Ways

Difficulty: Medium

Problem

A message of letters was encoded to digits: A→1, B→2, ... Z→26. Given the digit string, count how many ways it can be decoded back. "12" could be "AB" (1|2) or "L" (12) — two ways. Structurally this is Climbing Stairs, but the zeros and the 26-limit turn it into an edge-case gauntlet.

Example

Input: s = "226"
Output: 3
Explanation: "2|2|6" = BBF, "22|6" = VF, "2|26" = BZ — three decodings.

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