Count Number of Texts

Problem Description

Alice is texting Bob using her phone. The mapping of digits to letters determines how many times she needs to press a key to get a particular letter. Due to an error in transmission, Bob received a string of pressed keys instead of Alice's original message. Given this string, the task is to count the total number of possible text messages Alice could have sent.

Key Insights

• Each digit maps to a specific number of letters, where pressing a key corresponds to selecting a letter.
• The number of letters available for each digit varies, affecting the total combinations.
• We can use dynamic programming to count possible combinations based on the sequences of digits pressed.
• The result needs to be calculated modulo (10^9 + 7) to handle large numbers.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the pressedKeys string. Each character is processed once. Space Complexity: O(1), since we use a fixed number of variables regardless of the input size.

Solution

To solve the problem, we can use dynamic programming to keep track of the number of ways to form messages up to each character in the pressedKeys string. We initialize a list to store the number of combinations for each position, updating it based on the key presses and the number of letters that can be formed with those presses.

1. Create a mapping for each digit to the number of letters it corresponds to.
2. Initialize a dynamic programming array where dp[i] represents the number of ways to decode the string up to the ith position.
3. Iterate through the pressedKeys string:
   • For each digit, determine how many consecutive times it has been pressed.
   • Update the dp array based on the number of letters available for the digit and the previous counts.
4. Return the last value in the dp array, modulo (10^9 + 7).

Code Solutions