loading

Decode Ways — Step-by-Step Visualization

mediumLeetCode #91StringDynamic Programming

A message containing letters from A-Z can be encoded into numbers using the mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a string `s` containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

Algorithm Pattern

Linear Dynamic Programming

Key Idea

At any index `i`, the number of ways to decode the substring `s[i:]` depends on: (1) whether `s[i]` is a valid single-digit code ('1'-'9') and (2) whether `s[i...i+1]` is a valid two-digit code ('10'-'26'). This allows us to build the solution using the recurrence `dp[i] = dp[i+1] + dp[i+2]` (where applicable).

Step-by-Step Approach

  1. Initialize a `dp` array of size `n + 1`, where `n` is the length of `s`.
  2. Base case: `dp[n] = 1` (an empty string has one way to be decoded).
  3. Iterate from `i = n - 1` down to `0`.
  4. If `s[i]` is not '0', then `dp[i] += dp[i+1]` (valid single-digit decoding).
  5. If the two-character substring `s[i...i+1]` is between '10' and '26' (inclusive), then `dp[i] += dp[i+2]` (valid two-digit decoding).
  6. The answer is stored in `dp[0]`.

Common Gotchas

  • A leading '0' is invalid and results in 0 ways to decode that branch.
  • Be careful with indexing when checking for two-digit codes at the end of the string.

Related Problems

← All problems