{x}
blog image

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:
"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.

 

Constraints:

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

Solution Explanation: Count Number of Texts

This problem involves calculating the number of possible text messages that could have generated a given string of pressed keys. The key insight is that consecutive identical digits can represent multiple letters, leading to multiple possible message combinations. We can solve this using dynamic programming with an optimized approach for grouping identical digits.

Approach: Grouping and Dynamic Programming

  1. Grouping: The input string pressedKeys is first processed to group consecutive identical digits. This is because the number of ways to interpret a sequence of identical digits is independent of the other digits in the string. For example, "22233" becomes groups of ["222", "33"].

  2. Dynamic Programming: For each group, we use dynamic programming to determine the number of possible letter combinations. We use two arrays, f and g, to store the number of ways for groups of length i:

    • f[i] represents the number of ways to interpret a group of length i for digits 2, 3, 4, 5, 6, 8 (which map to 3 letters each).
    • g[i] represents the number of ways to interpret a group of length i for digits 7 and 9 (which map to 4 letters each).

  3. Recurrence Relations: The recurrence relations for f[i] and g[i] are:

    • f[i] = f[i-1] + f[i-2] + f[i-3] (for i ≥ 3) – A group of length i can be interpreted as one letter from the last character, or two letters from the last two characters, or three letters from the last three characters.
    • g[i] = g[i-1] + g[i-2] + g[i-3] + g[i-4] (for i ≥ 4) – Similar to f[i], but we consider groups of up to 4 characters since each digit can represent 4 different letters in this case.

  4. Base Cases: The base cases for f and g are: f[0] = f[1] = 1, f[2] = 2, g[0] = g[1] = 1, g[2] = 2, g[3] = 4.

  5. Result: After calculating the f and g arrays, we iterate over the grouped digits, multiplying the number of ways for each group (obtained from f or g based on the digit). The final product, modulo 109 + 7 (to handle large results), represents the total number of possible text messages.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of pressedKeys. The dynamic programming arrays f and g are pre-computed (or computed once only for the input size). The grouping and final calculation take linear time.

  • Space Complexity: O(N) in the worst case (if all digits are the same), to store the f and g arrays. In practice, we can optimize this further in most programming languages to avoid explicit storage of the complete arrays.

Code Implementation (Python)

mod = 10**9 + 7
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(100000):  # Precompute f and g arrays up to a large enough size
    f.append((f[-1] + f[-2] + f[-3]) % mod)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)
 
from itertools import groupby
 
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for c, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if c in "79" else f[m]) % mod
        return ans

The code in other languages (Java, C++, Go) follows the same logic, using appropriate data structures and syntax for each language. The key is the efficient pre-computation of the dynamic programming arrays and the grouping of identical characters.