A message made of capital letters was turned into digits by replacing each letter with its position in the alphabet: A becomes 1, B becomes 2, and so on up to Z, which becomes 26. The letters' codes were written one after another with nothing in between.
You get the digit string s. Return the number of different letter messages that could have produced it. Cut s into pieces, each piece one letter's code: a code is a number from 1 to 26 written without a leading zero, so "5" is a code but "05" and "0" are not. If s can't be cut that way at all, return 0.
The cuts 2|1|5, 21|5 and 2|15 give BAE, UE and BO.
A 0 can only be the second digit of 10 or 20. Here it must go with the 2 before it, which leaves 1|20|1 (ATA) as the only cut.
60 is larger than 26, and 0 on its own is not a code, so nothing works.
Constraints
1 <= s.length <= 100s holds only the digits 0–9, and may start with 0.Look at how the last piece of a cut can end: it is either the last digit alone or the last two digits together. So the ways to cut the first i digits are built from the ways for the first i − 1 and the first i − 2.
Look at how a cut of the whole string ends. Its last piece is either the last digit on its own or the last two digits together. Nothing else is possible, since every code is one or two digits long.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
3