## DEV Community

Abhishek Chaudhary

Posted on

# Count Number of Texts

Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

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.
• Note that 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.

• For example, when Alice sent the message `"bob"`, Bob received the string `"2266622"`.

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 `109 + 7`.

Example 1:

Input: pressedKeys = "22233"
Output: 8
Explanation:
The possible text messages Alice could have sent are:
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.

Constraints:

• `1 <= pressedKeys.length <= 105`
• `pressedKeys` only consists of digits from `'2'` - `'9'`.

SOLUTION:

``````class Solution:
def ways(self, m, n):
if m == 0:
return 1
if (m, n) in self.cache:
return self.cache[(m, n)]
ways = 0
for i in range(1, min(m, n) + 1):
ways += self.ways(m - i, n)
self.cache[(m, n)] = ways
return ways

def countTexts(self, pressedKeys: str) -> int:
self.cache = {}
keys = [0, 0, 3, 3, 3, 3, 3, 4, 3, 4]
n = len(pressedKeys)
i = 0
ways = 1
while i < n:
ctr = 1
while i < n - 1 and pressedKeys[i] == pressedKeys[i + 1]:
i += 1
ctr += 1
i += 1
c = pressedKeys[i - 1]
ways = (ways * self.ways(ctr, keys[int(c)])) % (10 ** 9 + 7)
return ways
``````