Leecode刷题C语言之统计打字方案数

执行结果:通过

执行用时和内存消耗如下：

 

 

 

int countTexts(char* pressedKeys) {int m = 1000000007;int n = strlen(pressedKeys);long long dp3[100001] = {1, 1, 2, 4};   // 连续按多次 3 个字母按键对应的方案数long long dp4[100001] = {1, 1, 2, 4};   // 连续按多次 4 个字母按键对应的方案数for (int i = 4; i <= n; ++i) {dp3[i] = (dp3[i-1] + dp3[i-2] + dp3[i-3]) % m;dp4[i] = (dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m;}long long res = 1;   // 总方案数int cnt = 1;   // 当前字符连续出现的次数for (int i = 1; i < n; ++i) {if (pressedKeys[i] == pressedKeys[i-1]) {++cnt;} else {// 对按键对应字符数量讨论并更新总方案数if (pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9') {res = (res * dp4[cnt]) % m;} else {res = (res * dp3[cnt]) % m;}cnt = 1;}}// 更新最后一段连续字符子串对应的方案数if (pressedKeys[n-1] == '7' || pressedKeys[n-1] == '9') {res = (res * dp4[cnt]) % m;} else {res = (res * dp3[cnt]) % m;}return res;
}

解题思路：

1. 初始化常量：
   • m 是结果需要取模的数值，以避免整数溢出，这里设为 1000000007（一个大质数）。
   • n 是输入字符串 pressedKeys 的长度，即按键的总次数。
2. 动态规划数组初始化：
   • dp3[i] 表示连续按 i 次一个3个字母按键（如2, 3, 5, 6, 8）可以形成的不同文本数量。
   • dp4[i] 表示连续按 i 次一个4个字母按键（如7, 9）可以形成的不同文本数量。
   • 初始值 dp3[1] = dp3[2] = 1（因为按1次或2次只能选择第一个字母），dp3[3] = 2（第三次可以选择第一个或第二个字母），dp3[4] = 4（第四次可以选择前四个字母的任意组合）。
   • dp4 的初始化同理。
3. 填充动态规划数组：
   • 使用循环从4到n填充 dp3 和 dp4 数组。每个数组的元素是前面几个元素的和（因为每次按键可以选择前面所有未选择过的字母）。
4. 计算总方案数：
   • 初始化 res 为1，表示总方案数。
   • 初始化 cnt 为1，表示当前字符连续出现的次数。
   • 遍历 pressedKeys 字符串，对于每个字符：
     • 如果当前字符与前一个字符相同，则增加 cnt。
     • 如果不同，则根据前一个字符（是3个字母键还是4个字母键）和 cnt 的值，更新 res（乘以对应的 dp3[cnt] 或 dp4[cnt]），并重置 cnt 为1。
5. 处理最后一个字符：
   • 循环结束后，还需要根据最后一个字符所属的键类型和它的连续次数 cnt，更新 res。
6. 返回结果：
   • 返回 res，即总方案数。

总结：

• 通过动态规划计算每个键连续按多次时可能的文本组合数。
• 遍历输入字符串，根据每个字符和前一个字符的关系，以及字符所属的键类型（3个字母还是4个字母），累计计算总方案数。
• 结果对 1000000007 取模，防止溢出。