Decode Ways
A message containing letters A-Z can be encoded as numbers: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".
Given a string s containing only digits, return the number of ways to decode it.
To decode, split s into groups of one or two digits where every group maps to a letter. A group with a leading zero (such as "06") is not a valid code, and "0" on its own maps to nothing. If no valid decoding exists, return 0.
Example
226
3
- Input:
sis a string of digits, here226. A decoding splits it into consecutive groups of one or two digits, and every group must be a code from to . - Splitting
226: there are three valid ways to cut it:- B, B, F, giving 'BBF'
- V, F, giving 'VF'
- B, Z, giving 'BZ'
- Ruled out: reading all three digits as one group is not allowed, since a code has at most two digits (and anyway).
- Output: the count of valid splittings, . Only the number is returned, not the decoded strings.
- Notice: both pairs here, and , are , so each adds a split. For the input "27" the pair is too big, leaving only 'BG', so the answer is . A zero can never stand alone and a group like "06" is not a code, so the input "06" has decodings.
Constraints
- 1 <= len(s) <= 100
- s contains only digits and may contain leading zeros