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.
's', Alice has to press '7' four times. Similarly, to add the letter 'k', Alice has to press '5' twice.'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.
"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 <= 105pressedKeys only consists of digits from '2' - '9'.This approach uses a dynamic programming array where dp[i] represents the number of ways to decode the substring pressedKeys[0..i]. We iterate over the string while keeping track of contiguous segments of the same digit. Depending on the digit, the maximum possible number of presses for letters range from 3 to 4. We update our dp array by considering these possible decompositions.
The solution uses a dynamic programming array `dp` where `dp[i]` represents the number of possible messages up to the i-th character. For each position, it checks up to the maximum number of possible key presses (3 or 4) to calculate the combinations possible leading up to that point, leveraging contiguous segments of the same digit. The result at `dp[n]` gives the total combinations for the entire string.
JavaScript
C
C++
Java
C#
Time Complexity: O(n), Space Complexity: O(n) where n is the length of the input string.
NUMBER OF ISLANDS - Leetcode 200 - Python • NeetCode • 384,140 views views
Watch 9 more video solutions →Practice Count Number of Texts with our built-in code editor and test cases.
Practice on FleetCode