文章

[LeetCode] 每日一题 2266. 统计打字方案数

题目链接

https://leetcode.cn/problems/count-number-of-texts

题目描述

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 数组:

  1. 对于每个字符 pressedKeys[i],如果它与前一个字符相同,那么 Alice 有多种可能性:

    • 按了 1 次,得到一个字符

    • 按了 2 次,得到另一个字符,等等

  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 次的情况。这个题目不仅考查了基础的动态规划思想,也考察了我们在复杂递推条件下如何合理地设计状态转移

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0