#2266
Count Number of Texts
specialist · 870 · lc medium +31 · verified · 50% accepted · 940 likes · top 38%
Description
Alice texts Bob using a phone keypad where each key maps to letters. A letter is entered by pressing its key a number of times equal to its position among that key's letters.
- For example, 's' requires pressing '7' four times, and 'k' requires pressing '5' twice.
- Digits '0' and '1' have no letter mappings and are never used by Alice.
Due to a transmission error, Bob only received the raw sequence of key presses, not the message.
- For example, when Alice sent "bob", Bob received "2266622".
Given the string pressedKeys that Bob received, return the number of distinct text messages Alice could have sent, modulo 109 + 7.
Example 1:
Input: pressedKeys = "22233"
Output: 8
Explanation:
The possible text messages Alice could have sent are:
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce".
Since there are 8 possible messages, we return 8.
Example 2:
Input: pressedKeys = "222222222222222222222222222222222222"
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.
Code
1
2
3