统计打字方案数
难度:
标签:
题目描述
Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
- 比方说，为了按出字母
's'，Alice 需要按'7'四次。类似的， Alice 需要按'5'两次得到字母'k'。 - 注意，数字
'0'和'1'不映射到任何字母，所以 Alice 不 使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
- 比方说，Alice 发出的信息为
"bob"，Bob 将收到字符串"2266622"。
给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：pressedKeys = "22233" 输出：8 解释： Alice 可能发出的文字信息包括： "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。 由于总共有 8 种可能的信息，所以我们返回 8 。
示例 2：
输入：pressedKeys = "222222222222222222222222222222222222" 输出：82876089 解释： 总共有 2082876103 种 Alice 可能发出的文字信息。 由于我们需要将答案对 109 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。
提示：
1 <= pressedKeys.length <= 105pressedKeys只包含数字'2'到'9'。
代码结果
运行时间: 94 ms, 内存: 24.8 MB
/*
* Problem: Calculate the number of possible text messages Alice could have sent to Bob using Java Streams.
*
* Solution approach:
* 1. Use dynamic programming to keep track of the number of ways to interpret each prefix of the input.
* 2. Leverage Java Streams to process the input string and calculate the possible combinations.
* 3. Use a modulo operation to keep the result within the range [0, 10^9 + 7].
*/
import java.util.stream.IntStream;
public class SolutionStream {
public int countTexts(String pressedKeys) {
int MOD = 1000000007;
int n = pressedKeys.length();
int[] dp = new int[n + 1];
dp[0] = 1;
IntStream.range(1, n + 1).forEach(i -> {
dp[i] = dp[i - 1];
if (i > 1 && pressedKeys.charAt(i - 1) == pressedKeys.charAt(i - 2)) {
dp[i] = (dp[i] + dp[i - 2]) % MOD;
if (i > 2 && pressedKeys.charAt(i - 1) == pressedKeys.charAt(i - 3)) {
dp[i] = (dp[i] + dp[i - 3]) % MOD;
if (i > 3 && (pressedKeys.charAt(i - 1) == '7' || pressedKeys.charAt(i - 1) == '9') && pressedKeys.charAt(i - 1) == pressedKeys.charAt(i - 4)) {
dp[i] = (dp[i] + dp[i - 4]) % MOD;
}
}
}
});
return dp[n];
}
}
解释
方法:
题解采用了动态规划的思路。首先，根据题意，数字键2-9上的字母可以有不同的按键次数（比如2对应的字母可以通过按1次、2次或3次得到），而数字7和9可以按4次。因此，为了计算任意长度m的数字序列所能代表的文本信息数，我们预先计算了两个动态规划数组f和g。数组f存储了按键次数最多为3的情况下，长度为m的序列的组合数；数组g存储了按键次数最多为4的情况下的组合数。这种预计算保证了后续计算的效率。在解决方案的主函数中，使用groupby函数来聚合连续的相同数字，然后根据这些数字的数量和种类，利用预先计算的f或g数组来快速得到结果。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在动态规划数组f和g的初始化中，为什么只初始化前四个元素的值？
▷🦆
数组f和g的预计算过程中，具体是如何确定下一个元素值的，能详细解释其递推公式吗？
▷🦆
为什么在处理数字'7'或'9'时使用数组g，而对其他数字使用数组f？这种区分的理由是什么？
▷🦆
在使用groupby聚合连续相同数字时，为什么需要将groupby的结果转换成列表来计算长度？这样做有没有可能的性能影响？
▷