A message containing letters from A-Z can be encoded into numbers using: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a string s containing only digits, return the number of ways to decode it.
Examples
Input:s = '12'
Output:2
Decoded as 'AB' (1 2) or 'L' (12).
Input:s = '226'
Output:3
Decoded as 'BZ' (2 26), 'VF' (22 6), or 'BBF' (2 2 6).
Constraints
• 1 <= s.length <= 100
• s contains only digits and may contain leading zeroes.