Decode Ways

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?