2266. 统计打字方案数

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 取余 后返回。

代码

class Solution {
    public static final int length = 1000_01;
    public static final int[] three = new int[length];
    public static final int[] four = new int[length];
    public static final int mod = 1000_000_007;

    // 预计算三键和四键的动态规划结果
    static {
        three[0] = 1;
        three[1] = 1;
        three[2] = 2;
        for (int i = 3; i < length; i++) {
            three[i] = (int)(((long) three[i - 1] + three[i - 2] + three[i - 3]) % mod);
        }
        four[0] = 1;
        four[1] = 1;
        four[2] = 2;
        four[3] = 4;
        for (int i = 4; i < length; i++) {
            four[i] = (int)(((long) four[i - 1] + four[i - 2] + four[i - 3] + four[i - 4]) % mod);
        }
    }
    int[] num = new int[]{0, 0, 3, 3, 3, 3, 3, 4, 3, 4};

    public int countTexts(String pressedKeys) {
        int n = pressedKeys.length();
        int cnt = 1;
        long ans = 1;
        int cur = pressedKeys.charAt(0) - '0';
        for (int i = 1; i < n; i++) {
            if (pressedKeys.charAt(i)!= pressedKeys.charAt(i - 1)) {
                if (num[cur] == 3)
                    ans = (ans * three[cnt]) % mod;
                else
                    ans = (ans * four[cnt]) % mod;
                cur = pressedKeys.charAt(i) - '0';
                cnt = 1;
            } else {
                cnt++;
            }
        }
        if (num[cur] == 3)
            ans = (ans * three[cnt]) % mod;
        else
            ans = (ans * four[cnt]) % mod;
        return (int) ans % mod;
    }
}