【Leetcode 每日一题】2266. 统计打字方案数

问题背景

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\le pressedKeys.length\le 10^5$
• $pressedKeys$ 只包含数字 ‘2’ 到 ‘9’ 。

解题过程

形成了某种奇怪的条件反射，一开始自己做用的是回溯。
实际上将这个问题看作拓展版的 爬楼梯，可以先打表，然后直接查出结果。

具体实现

class Solution {
    private static final int MOD = 1000000007;
    private static final int MAX_N = 100010;
    private static final long[] f = new long[MAX_N];
    private static final long[] g = new long[MAX_N];

    // 在静态代码块预处理所有可能的结果
    static {
        f[0] = g[0] = 1;
        f[1] = g[1] = 1;
        f[2] = g[2] = 2;
        f[3] = g[3] = 4;
        for (int i = 4; i < MAX_N; i++) {
            f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD;
            g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % MOD;
        }
    }

    public int countTexts(String pressedKeys) {
        long res = 1;
        int index = 0;
        for (int i = 0; i < pressedKeys.length(); i++) {
            char c = pressedKeys.charAt(i);
            index++;
            if (i == pressedKeys.length() - 1 || c != pressedKeys.charAt(i + 1)) {
                // 根据实际的字符来得到可能性的总数，用到了乘法公式
                res = res * (c != '7' && c != '9' ? f[index] : g[index]) % MOD;
                index = 0;
            }
        }
        return (int) res;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/145240127

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！