[LeetCode] 每日一题 2266. 统计打字方案数
题目链接
题目描述
Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
为了 打出 一个字母,Alice 需要 按 对应字母 i
次,i
是该字母在这个按键上所处的位置。
比方说,为了按出字母
's'
,Alice 需要按'7'
四次。类似的, Alice 需要按'5'
两次得到字母'k'
。注意,数字
'0'
和'1'
不映射到任何字母,所以 Alice 不 使用它们。
但是,由于传输的错误,Bob 没有收到 Alice 打字的字母信息,反而收到了 按键的字符串信息 。
比方说,Alice 发出的信息为
"bob"
,Bob 将收到字符串"2266622"
。
给你一个字符串 pressedKeys
,表示 Bob 收到的字符串,请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大,将它对 10^9 + 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 % (10^9 + 7) = 82876089 。
提示
1 <= pressedKeys.length <= 10^5
pressedKeys
只包含数字'2'
到'9'
。
解题思路
这道题目给定了一个字符串 pressedKeys
,表示 Bob 收到的按键信息,我们需要找出 Alice 可能发送的文字信息的数量。通过观察题目中的按键映射,我们可以得出一个结论:如果当前按键字符与前一个相同,则 Alice 可能按了多个相同的数字来输入同一个字母。因此,问题的核心是如何计算每个按键位置可能的字符数,并通过动态规划推导出最终的结果
我一开始就想到了使用动态规划来解决这个问题。我们定义一个 dp[i]
来表示前 i
个字符可能的不同的字母信息组合数。然后我们通过以下的递推关系来更新 dp
数组:
对于每个字符
pressedKeys[i]
,如果它与前一个字符相同,那么 Alice 有多种可能性:按了 1 次,得到一个字符
按了 2 次,得到另一个字符,等等
特别地,数字 '7' 和 '9' 都有 4 个字符对应,所以它们的递推关系需要考虑到最多连续按 4 次的情况
通过这种递推,我们最终可以得到所有可能的信息组合数
代码实现
class Solution {
int MOD = 1000000007;
public int countTexts(String pressedKeys) {
int len = pressedKeys.length();
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= len; i++) {
dp[i] = dp[i - 1];
char c = pressedKeys.charAt(i - 1);
if (c == pressedKeys.charAt(i - 2)) {
// 如果连续两次相同,添加前两种可能性
dp[i] = (dp[i] + dp[i - 2]) % MOD;
if (i > 2 && c == pressedKeys.charAt(i - 3)) {
// 如果连续三次相同,添加前三种可能性
dp[i] = (dp[i] + dp[i - 3]) % MOD;
if ((c == '7' || c == '9') && i > 3 && c == pressedKeys.charAt(i - 4)) {
// 如果是 '7' 或 '9' 并且连续四次相同,添加前四种可能性
dp[i] = (dp[i] + dp[i - 4]) % MOD;
}
}
}
}
return dp[len];
}
}
复杂度分析
时间复杂度:O(n),其中
n
是输入字符串pressedKeys
的长度。每次迭代都只做常数时间的操作,所以整体时间复杂度是 O(n)空间复杂度:O(n),我们使用了一个
dp
数组来存储每个状态的可能组合数,数组的大小为n + 1
总结
这道题目考察了动态规划的运用,通过递推关系动态计算每个按键对应的可能字符数量,并逐步累积可能的结果。由于按键字符相同的情况下会有多个可能性,所以我们要通过递推关系将这些可能性逐个考虑进去。对于 '7' 和 '9' 这样的特殊情况,我们还需要考虑最多按 4 次的情况。这个题目不仅考查了基础的动态规划思想,也考察了我们在复杂递推条件下如何合理地设计状态转移
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。