A secret message uses numbers for the letters of the alphabet: "1" is A, "2" is B, and so on up to "26" which is Z.
To read a message made of digits, cut it into groups. Each group must be one of the numbers 1 to 26 written without a zero at the front. So "6" and "26" are fine, but "06" and "27" are not.
The same digits can often be cut in more than one way. For example, "1126" can be read in 5 ways:
1 1 2 6, which is AABF1 12 6, which is ALF11 2 6, which is KBF1 1 26, which is AAZ11 26, which is KZ
Given a string s of digits, return in how many ways it can be read. If it cannot be read at all, return 0.
Examples
Example 1:
Input: s = "111"
Output: 3
Explanation: The ways are 1-1-1 (AAA), 11-1 (KA) and 1-11 (AK). That is 3 ways.
Example 2:
Input: s = "227"
Output: 2
Explanation: The ways are 2-2-7 (BBG) and 22-7 (VG). The group 27 is too big for a letter.
Example 3:
Input: s = "301"
Output: 0
Explanation: A group cannot start with 0, and "30" is bigger than 26, so the 0 can never be used. There is no way.