A message containing letters from A-Z can be encoded into numbers using the mapping: 'A' = 1, 'B' = 2, ..., 'Z' = 26.
Given a string s containing only digits, return the number of ways to decode it. A digit sequence may have multiple valid decodings. For example, "11106" can be decoded as "AAJF" (1 1 10 6) or "KJF" (11 10 6). Note that "06" is not valid because "6" and "06" are different in the mapping.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be decoded because leading zeros are invalid. There is no character mapped to 06.
1 <= s.length <= 100s contains only digits '0' through '9'