2266. Count Number of Texts Medium

1/**
2 * [2266] Count Number of Texts
3 *
4 * Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.
5 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png" style="width: 200px; height: 162px;" />
6 * 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.
7 * 
8 * 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.
9 * Note that the digits '0' and '1' do not map to any letters, so Alice does not use them.
10 * 
11 * However, due to an error in transmission, Bob did not receive Alice's text message but received a string of pressed keys instead.
12 * 
13 * For example, when Alice sent the message "bob", Bob received the string "2266622".
14 * 
15 * Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.
16 * Since the answer may be very large, return it modulo 10^9 + 7.
17 *  
18 * 
19 * Example 1:
20 * 
21 * Input: pressedKeys = "22233"
22 * Output: 8
23 * Explanation:
24 * The possible text messages Alice could have sent are:
25 * "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce".
26 * Since there are 8 possible messages, we return 8.
27 * 
28 * Example 2:
29 * 
30 * Input: pressedKeys = "222222222222222222222222222222222222"
31 * Output: 82876089
32 * Explanation:
33 * There are 2082876103 possible text messages Alice could have sent.
34 * Since we need to return the answer modulo 10^9 + 7, we return 2082876103 % (10^9 + 7) = 82876089.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 1 <= pressedKeys.length <= 10^5
40 * pressedKeys only consists of digits from '2' - '9'.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/count-number-of-texts/
46// discuss: https://leetcode.com/problems/count-number-of-texts/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn count_texts(pressed_keys: String) -> i32 {
52        const MOD: i32 = 10_i32.pow(9) + 7;
53        let len = pressed_keys.len();
54        let mut dp = vec![0; len + 1];
55        dp[0] = 1;
56        let chs: Vec<char> = pressed_keys.chars().collect();
57        for n in 1..chs.len() + 1 {
58            dp[n] = dp[n - 1] % MOD;
59            if n >= 2 && chs[n - 1] == chs[n - 2] {
60                dp[n] = (dp[n] + dp[n - 2]) % MOD;
61                if n >= 3 && chs[n - 2] == chs[n - 3] {
62                    dp[n] = (dp[n] + dp[n - 3]) % MOD;
63                    if n >= 4 && chs[n - 3] == chs[n - 4] && (chs[n - 1] == '7' || chs[n - 1] == '9') {
64                        dp[n] = (dp[n] + dp[n - 4]) % MOD;
65                    }
66                }
67            }
68        }
69        dp[len]
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_2266_1() {
81        assert_eq!(Solution::count_texts("22233".into()), 8);
82    }
83
84    #[test]
85    fn test_2266_2() {
86        assert_eq!(Solution::count_texts("222222222222222222222222222222222222".into()), 82876089);
87    }
88}
89