Decode Ways

Gas Station

Daily Temperatures

Count how many valid A1Z26 decodings a digit string can represent.

A message was encoded using the mapping `1 -> A`, `2 -> B`, ..., `26 -> Z`. Given a string of digits, return how many different ways it can be decoded. A leading zero is never valid by itself, and two-digit decodings are only allowed for values from `10` through `26`.

**Input / output**
- Input: `s: string` containing only digits
- Output: integer number of valid decodings

**Examples**
1. `s = "12"` returns `2` because it can be decoded as `AB` or `L`.
2. `s = "226"` returns `3` because the valid decodings are `BZ`, `VF`, and `BBF`.
3. `s = "06"` returns `0` because no decoding may start with `0`.

**Constraints**
- `1 <= s.length <= 100`
- `s` contains only digits

**Target complexity**
- Aim for `O(n)` time and `O(1)` extra space.

**Hints**
1. Let `dp[i]` mean: how many ways can the suffix starting at index `i` be decoded?
2. At each position, you may use one digit, and sometimes also two digits, if that pair is between `10` and `26`.

**Follow-up**
How would the recurrence change if the encoding also allowed `*` to mean any digit from `1` to `9`?

- The choice at index `i` only affects the remaining suffix after consuming one or two digits.
- That makes this a natural dynamic-programming problem over suffixes.

Define the suffix state

- A recursive search tries one-digit and two-digit decodes whenever they are valid.
- Without memoization, repeated suffixes explode exponentially.

Brute-force baseline

- If `s[i]` is `0`, there are `0` ways from that position.
- Otherwise, start with the number of ways from `i + 1` (taking one digit).
- If `s[i:i+2]` is between `10` and `26`, also add the number of ways from `i + 2`.

Rolling DP transition

A right-to-left scan only needs the next two DP values, so the suffix DP compresses to constant space.

Final solution (all languages)

- Treating `0` as a standalone letter, which is never allowed.
- Allowing any two-digit number under `30`; only `10` through `26` are valid pairs.
- Follow-up: when `*` is introduced, the recurrence stays similar but each branch contributes multiple counts instead of just one.