Decode Ways

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

At index `i`, zero yields `0` single-digit decodings (`"0"` is invalid standalone). Otherwise inherit `dp[i+1]` (1-digit `1..9`) plus `dp[i+2]` whenever `s[i:i+2]` lies in `10..26`.

2. Complexity Bounds & Proof

Backward pass relies exclusively on the next two DP states (`dp1`, `dp2`), yielding O(N) time and O(1) space.

3. Minimal Idiomatic Code

def numDecodings(s: str) -> int:
    dp1, dp2 = 1, 0
    for i in range(len(s) - 1, -1, -1):
        cur = 0 if s[i] == '0' else dp1
        if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
            cur += dp2
        dp1, dp2 = cur, dp1
    return dp1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Leading zero `"06"` is invalid, and internal `"100"` produces zero ways (do not advance past `"0"` blindly). - Writing `10 <= int(s[i:i+2]) <= 26` cleanly prevents `"05"` from matching 2-digit rule.
Follow-ups:- Decode Ways II introduces wildcard `"*"` characters multiplying single-digit options by `9` and 2-digit options across `11..26`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Climbing Stairs (O(N))Word Break (O(N * W * L))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.