Count Number of Texts

Alice is texting Bob using her phone. The mapping of digits to letters is the standard phone keypad mapping:

  • 2: 'a', 'b', 'c'
  • 3: 'd', 'e', 'f'
  • 4: 'g', 'h', 'i'
  • 5: 'j', 'k', 'l'
  • 6: 'm', 'n', 'o'
  • 7: 'p', 'q', 'r', 's'
  • 8: 't', 'u', 'v'
  • 9: 'w', 'x', 'y', 'z'

In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.

  • For example, to add the letter 's', Alice has to press '7' four times.
  • Similarly, to add the letter 'k', Alice has to press '5' twice.
  • The digits '0' and '1' do not map to any letters, so Alice does not use them.

However, due to an error in transmission, Bob did not receive Alice's text message but received a string of pressed keys instead.

Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1
InputpressedKeys = "22233"
Output8
The possible text messages Alice could have sent are "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce", so there are 8 possible messages.
Example 2
InputpressedKeys = "222222222222222222222222222222222222"
Output82876089
There are 2082876103 possible text messages Alice could have sent, so modulo 10^9 + 7 the answer is 82876089.

Constraints

  • 1 <= pressedKeys.length <= 10^5
  • pressedKeys only consists of digits from '2' - '9'.

Asked at 3 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate