Messages Behind Key Presses

Medium

On a keypad phone, letters sit on the digit keys: | Key | Letters | |---|---| | 2 | abc | | 3 | def | | 4 | ghi | | 5 | jkl | | 6 | mno | | 7 | pqrs | | 8 | tuv | | 9 | wxyz | To type a letter you press its key as many times as the letter's position on that key: "a" is one press of 2, "c" is three presses of 2, "s" is four presses of 7. Keys 0 and 1 are not used. The receiver got only the raw presses with no pauses, the string presses. For example, the word "bob" turns into "2266622". Return how many different messages could produce this string. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

presses='4433' → 4

"44" is "gg" or "h", and "33" is "dd" or "e". That makes 2 · 2 = 4 messages: "ggdd", "gge", "hdd", "he".

Example 2

presses='7777' → 8

Key 7 carries four letters, so four presses can also be the single letter "s". The splits of 4 are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 and 4: eight in total.

Example 3

presses='2' → 1

Constraints

1 ≤ len(presses) ≤ 10⁵
presses consists only of digits 2 through 9

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math String Dynamic Programming