91. Decode Ways
A secret message made of capital letters was turned into digits with the code A = 1, B = 2, … Z = 26, and the chunks were glued together with nothing in between. You receive the glued digit string s and must work out how many different letter messages could have produced it.
The catch is ambiguity: "12" might have been AB (1, then 2) or L (12). A grouping only counts when every chunk is a number from 1 to 26 written without a leading zero — so "06" can never be a chunk, while "6" can.
Given the digit string s, return the total number of ways to split it into valid chunks. If no split works at all (for example the string starts with 0), return 0.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" decodes as (1)(2) → AB or as (12) → L, so there are 2 messages.
Example 2:
Input: s = "226"
Output: 3
Explanation: (2)(2)(6) → BBF, (22)(6) → VF, and (2)(26) → BZ all work.
Example 3:
Input: s = "06"
Output: 0
Explanation: A chunk may not start with 0, so "06" has no valid decoding.
Constraints:
- 1 ≤ s.length ≤ 100
- s contains only digits 0-9
- The answer fits in a 32-bit signed integer.
Hints:
The number of ways to decode the first i characters only depends on the counts for the first i−1 and i−2 characters — a Fibonacci-shaped recurrence.
At position i, the digit s[i−1] alone extends every decoding of the first i−1 characters (unless it is 0), and the pair s[i−2..i−1] extends every decoding of the first i−2 characters when it reads as 10–26.
Zeros do all the damage: a 0 must be absorbed as 10 or 20, otherwise the whole count collapses to zero.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "12"
Expected output: 2