题解 | 统计打字方案数

alt

题干分析

题设给予我们一个人通过老式九键输入的按钮顺序字符串，已知老式九键输入模式为按对应的数字按键k次定位到该数字按键表示的三个或四个字母中的第k个进行输入（注意不会循环）。要求我们通过所给的按键顺序字串推测可能的输入内容总数（结果对 $10^9+7$ 取余）

算法思路

拆分问题：

首先考虑全部按键顺序字串只有一种按键的情况：

如果没有按任何按键，输入内容视作空，仍然看作一种情况
如果只按一次某按键，输入内容唯一，即所按按键对应的第一个字母
如果按两次，要么对应两次第一字母，要么对应一次第二字母，共2种情况
如果按三次，对应三个第一字母，对应一个第二一个第一，先后关系导致计数+2，以及一次第三字母，共计4种情况

此后针对更长的单一按键顺序字串我们可以将字串后一个/两个/三个/四个按键视作一组，可能的输入结果数就是对应长度-1/-2/-3/-4的单一按键顺序字串对应的输入情况个数之和。同时由于按键映射字母有的有三个，有的有四个，因此需分开进行DP计算，不过总体类似

状态转移方程如下：

$dp3[i]=\sum_{j=1}^{3}dp3[i-j],i\ge4$

$dp4[i]=\sum_{j=1}^{4}dp4[i-j],i\ge4$

计算完成后我们再考虑拥有不同按键的按键顺序字串。由题此前单一按键的情况，将最终的按键顺序字串按照连续相同字符进划分，将其拆分为多个单一的按键顺序字串，根据乘法计数原理，最终结果便是这些单一按键顺序字串对应的情况数之间的乘积。

同时注意题设要求将结果对 $10^9+7$ 取余，因此每次针对结果情况的计算均需要追加取余操作。

实现代码

class Solution {
    const int M = 1000000007;

    int addMod(int a, int b) {
        long long tmp = static_cast<long long>(a) + b;
        return static_cast<int>(tmp % M);
    }

    int mulMod(int a, int b) {
        long long tmp = static_cast<long long>(a) * b;
        return static_cast<int>(tmp % M);
    }
public:
    int countTexts(string pressedKeys) {
        int n = pressedKeys.size();
        vector<int> dp3(n + 4); // 稍微开大一点，防止段错误，下同
        vector<int> dp4(n + 4);
        dp3[0] = dp4[0] = 1;
        dp3[1] = dp4[1] = 1;
        dp3[2] = dp4[2] = 2;
        dp3[3] = dp4[3] = 4;

        auto cal = [&]() {
            for (int i = 4; i <= n; ++i) {
                for (int j = 1; j <= 3; ++j) dp3[i] = addMod(dp3[i], dp3[i - j]);
                for (int j = 1; j <= 4; ++j) dp4[i] = addMod(dp4[i], dp4[i - j]);
            }
        };
        cal();

        int ans = 1, cnt = 0;
        for (int i = 0; i < n; ++i) {
            char c = pressedKeys[i];
            ++cnt;
            if (i == n - 1 || c != pressedKeys[i + 1]) {
                if (c == '7' || c == '9') ans = mulMod(ans, dp4[cnt]);
                else ans = mulMod(ans, dp3[cnt]);
                cnt = 0;
            }
        }

        return ans;
    }
};