2266. 统计打字方案数

发表于 分类于 阅读次数： Waline： 本文字数： 680 阅读时长 ≈ 2 分钟

考点

  • 线性DP
  • 划分DP

思路

一、问题建模

在传统手机九宫格输入法中，每个数字键对应若干个字母：

  • 数字 2, 3, 4, 5, 6, 8：对应 3 个字母
  • 数字 7, 9：对应 4 个字母

当某个数字被连续按下多次时，表示在该数字对应的字母中依次选择。例如：

  • "2" → a
  • "22" → aa 或 b
  • "222" → aaa / ab / ba / c

给定一个仅由 '2'–'9' 组成的字符串 pressedKeys，表示用户连续按键的结果，要求计算所有可能的文本解析方式数量，并对 10^9 + 7 取模。

二、动态规划设计

1. 状态定义

设 \[ f[i] \] 表示 前 \(i\) 个按键字符（即 pressedKeys[0..i-1]）可以组成的文本方案数。

2. 初始状态

  • 空字符串只有一种解析方式：

\[ f[0] = 1 \]

  • 单个字符也只有一种解析方式：

\[ f[1] = 1 \]

三、状态转移分析

考虑第 \(i\) 个按键字符（pressedKeys[i-1]）作为结尾。

1. 基本情况：单独成段

无论是否与前一个字符相同，都可以将第 \(i\) 个字符单独作为一个按键段： \[ f[i] \leftarrow f[i-1] \]

2. 合并连续相同数字

若当前字符可以与前面的字符合并，则可以形成一个更长的按键段。

  • 若数字为 7 或 9，最多允许连续按 4 次
  • 否则最多允许连续按 3 次

设连续段的起点为 \(j\)，则需要满足：

  • pressedKeys[j-1] == pressedKeys[i-1]
  • 段长度 \(i - j + 1 \le cnt\)

当区间 \([j, i]\) 作为一个整体字符时，其前缀部分为 \([1, j-1]\)，对应方案数为 \(f[j-1]\)，因此有转移： \[ f[i] \leftarrow f[i] + f[j-1] \]

3. 转移方程总结

\[ f[i] = f[i-1] + \sum_{\substack{j \le i-1 \\ \text{数字相同} \\ i-j+1 \le cnt}} f[j-1] \]

所有加法均在模 \(10^9 + 7\) 下进行。

四、复杂度分析

  • 每个位置最多向前枚举 3 或 4 个字符
  • 时间复杂度：

\[ O(n) \]

  • 空间复杂度：

\[ O(n) \]

五、最终答案

\[ \text{Answer} = f[n] \]

六、AC代码

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
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const int mod = 1e9 + 7;

    int countTexts(string pressedKeys) {
        long long f[maxn];
        int n = pressedKeys.size();

        // 边界条件
        f[0] = 1;  // 空前缀
        f[1] = 1;  // 单字符前缀

        for (int i = 2; i <= n; ++i) {
            // 情况 1：第 i 个字符单独作为一个按键段
            f[i] = f[i - 1];

            // 当前数字允许的最大连续次数
            int cnt = (pressedKeys[i - 1] == '7' || pressedKeys[i - 1] == '9') ? 4 : 3;

            // 向前合并连续相同数字
            int j = i - 1;
            while (j >= 1 &&
                   pressedKeys[j - 1] == pressedKeys[i - 1] &&
                   i - j + 1 <= cnt) {

                // 区间 [j, i] 作为一个整体字符
                f[i] = (f[i] + f[j - 1]) % mod;
                j--;
            }
        }

        return (int)f[n];
    }
};