golang 刷leetcode：统计打字方案数

alice在用手机给bob发送信息时，使用的按键和字母的对应关系如下图所示。

为了输入一个字母，Alice需要按对应按键的次数，等于该字母在按键上的位置。例如，要输入字母 's'，Alice需要按 '7' 四次；要输入字母 'k'，Alice需要按 '5' 两次。

需要注意的是，数字 '0' 和 '1' 没有对应的字母，因此Alice不会使用它们。

然而，由于传输错误，Bob收到的不是Alice发送的字母信息，而是按键的字符串信息。例如，Alice发送的信息为 "bob"，Bob会收到字符串 "2266622"。

立即学习“go语言免费学习笔记（深入）”；

现在给你一个字符串 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

Figstack

一个基于 Web 的AI代码伴侣工具，可以帮助跨不同编程语言管理和解释代码。

下载

解释：

总共有2082876103种Alice可能发送的文字信息。

由于需要对10^9 + 7取模，返回2082876103 % (10^9 + 7) = 82876089。

提示：

• 1
• pressedKeys 只包含数字 '2' 到 '9'。

解题思路：

1. 这个问题可以转化为爬楼梯问题，具体情况如下：

   A. 如果连续两个字符相同，可以爬1步或2步。

   B. 如果连续三个字符相同，可以爬1步、2步或3步。

   C. 如果连续四个或更多字符相同，且是7或9，可以爬1步、2步、3步或4步。

   D. 如果字符不相同，只能爬一步。

2. 这是一个类似于斐波那契数列的问题。

3. 可以通过动态规划来解决。

代码实现：

function countTexts(pressedKeys) {
    const dp = new Array(pressedKeys.length + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= pressedKeys.length; i++) {
        let tmp = 0;
        if (i >= 4 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3] && pressedKeys[i-1] === pressedKeys[i-4] && (pressedKeys[i-1] === '7' || pressedKeys[i-1] === '9')) {
            tmp = (dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]) % 1000000007;
        } else if (i >= 3 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3]) {
            tmp = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007;
        } else if (i >= 2 && pressedKeys[i-1] === pressedKeys[i-2]) {
            tmp = (dp[i-1] + dp[i-2]) % 1000000007;
        } else {
            tmp = dp[i-1];
        }
        dp[i] = tmp;
    }

    return dp[pressedKeys.length];
}

目前这个实现的空间复杂度是O(n)，但可以进一步优化到O(1)，因为我们只需要使用到dp数组中的四个变量。因此，可以使用一个长度为4的数组来优化空间复杂度。

优化后的代码：

function countTexts(pressedKeys) {
    const dp = [1, 1, 1, 1];

    for (let i = 1; i <= pressedKeys.length; i++) {
        let tmp = 0;
        if (i >= 4 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3] && pressedKeys[i-1] === pressedKeys[i-4] && (pressedKeys[i-1] === '7' || pressedKeys[i-1] === '9')) {
            tmp = (dp[3] + dp[2] + dp[1] + dp[0]) % 1000000007;
        } else if (i >= 3 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3]) {
            tmp = (dp[3] + dp[2] + dp[1]) % 1000000007;
        } else if (i >= 2 && pressedKeys[i-1] === pressedKeys[i-2]) {
            tmp = (dp[3] + dp[2]) % 1000000007;
        } else {
            tmp = dp[3];
        }

        dp[0] = dp[1];
        dp[1] = dp[2];
        dp[2] = dp[3];
        dp[3] = tmp;
    }

    return dp[3];
}