6058. 统计打字方案数

leetcode 6058. 统计打字方案数

题目：6058. 统计打字方案数

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 <= 105
• pressedKeys 只包含数字 ‘2’ 到 ‘9’ 。

方法：动态规划

思路： dp[i]表示以pressKey第i个位置上字符结尾的方案个数，chas[i]表示pressKey第i个位置上的字符，分情况讨论：

根据题目可知dp[-1] = 1、dp[0] = 1，即没有字符时方案数为1，以第0个位置上的字符结尾时方案数也为1。

对于非 ‘7’ 和 ‘9’ 按键：

• 当chas[i] != chas[i - 1]时，最后的按键情况只有一种，如 ‘1’ ，对应按出字符 ‘a’ ，所以方案数取决于 i - 1 位置上的方案数 ，dp[i] = dp[i - 1]
• 当chas[i] == chas[i - 1]时，最后的按键情况会有两种，如 ‘1’ 或者 ‘11’ ，对应按出字符 ‘a’ 、’b’ ，所以方案数应为 i - 1 位置上的方案数加上 i - 2 位置上的方案数，dp[i] = dp[i - 1] + dp[i - 2]
• 当chas[i] == chas[i - 1] == chas[i - 2]时，最后的按键情况会有三种，如 ‘1’ 或者 ‘11’ 或者 ‘111’ ，对应按出字符 ‘a’ 、’b’ 、’c’，所以方案数应为 i - 1 位置上的方案数加上 i - 2 位置上的方案数加上 i - 3 位置上的方案数，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

对于 ‘7’ 和 ‘9’ 按键，仍包含上述三种情况，此外，由于 ‘7’ 和 ‘9’ 按键上有4个字符，其还包含第四种情况：

• 当chas[i] == chas[i - 1] == chas[i - 2] == chas[i - 3]时，最后的按键情况会有四种，如 ‘1’ 或者 ‘11’ 或者 ‘111’ 或者 ‘1111’ ，对应按出字符 ‘p’ 、’q’ 、’r’ 、’s’，所以方案数应为 i - 1 位置上的方案数加上 i - 2 位置上的方案数加上 i - 3 位置上的方案数加上 i - 4 位置上的方案数，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]

状态转移方程为：
$$
\begin{cases}
dp[i] = 1, & \text {i = -1, i = 0} \\
dp[i] = dp[i - 1], & \text {chas[i] != chas[i - 1]} \\
dp[i] = dp[i - 1] + dp[i - 2], & \text {chas[i] = chas[i - 1]} \\
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3], & \text {chas[i] = chas[i - 1] = chas[i - 2]} \\
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4], & \text {chas[i] = chas[i - 1] = chas[i - 2] = chas[i - 3], 按键为 ‘7’ | ‘9’} \\
\end{cases}
$$
运行数据： 执行用时：17 ms，内存消耗：42.2 MB

复杂度分析：

• 时间复杂度：O(n)，n为pressedKeys字符串长度。
• 空间复杂度：O(n)，n为pressedKeys字符串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// LeetCode指定调用方法
public int countTexts(String pressedKeys) {
		
    int mod = (int) (1e9 + 7);
    int n = pressedKeys.length();
    char[] chas = pressedKeys.toCharArray();
    // dp[i]表示以pressKey第i个位置上字符结尾的方案个数
    long[] dp = new long[n];
    dp[0] = 1;

    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1];
        if (chas[i] == chas[i - 1]) {
            dp[i] += i >= 2 ? dp[i - 2] : 1;
            if (i >= 2 && chas[i] == chas[i - 2]) {
                dp[i] += i >= 3 ? dp[i - 3] : 1;
                if (i >= 3 && (chas[i] == '7' || chas[i] == '9') && chas[i] == chas[i - 3]) {
                    dp[i] += i >= 4 ? dp[i - 4] : 1;
                }
            }
        }
        dp[i] %= mod;
    }
    return (int)dp[n - 1];
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！