Loading...
Loading...
Loading...
Meena and her friend pass notes in class using a code: A is 1, B is 2, and so on up to Z, which is 26. They write the numbers next to each other with no spaces.
So 126 can be read as 1 2 6 (ABF), 12 6 (LF) or 1 26 (AZ). A group can never start with 0, so 06 is not 6, and a lone 0 is not a letter.
Given the digits of a note, print how many ways it can be read. Print the count modulo 10^9 + 7. Print 0 if the note cannot be read at all.
Example 1
Input
226
Output
3
The readings are 2 2 6, 22 6 and 2 26, so the answer is 3.
Example 2
Input
2101
Output
1
The 0 must join the 1 before it as 10, so the only reading is 2 10 1.
Try the problem first. Open one hint at a time.
Let ways[i] be the number of ways to read the first i digits. An empty start has ways[0] = 1.
The last group is either one digit (1 to 9) or two digits (10 to 26). Add ways[i - 1] or ways[i - 2] for each group that is valid.
A two-digit group must have a first digit that is not 0, so check that the number is at least 10.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor