#2266. 统计打字方案数

LeetCode 原题链接

#题目描述

老式手机的数字键盘中，一个按键对应多个字母：

2 -> abc    3 -> def
4 -> ghi    5 -> jkl
6 -> mno    7 -> pqrs
8 -> tuv    9 -> wxyz

输入字符串 pressedKeys 记录了按键顺序。连续按同一个数字不同次数，可以输入该按键上的不同字母。

例如数字 2：

按 1 次 2 -> a
按 2 次 2 -> b
按 3 次 2 -> c

数字 7 和 9 各对应 4 个字母，所以最多可以连续按 4 次；其他数字最多连续按 3 次。

请计算 pressedKeys 可能表示多少种文本，结果对 10⁹ + 7 取模。

输入：pressedKeys = "22233"
输出：8

#先理解如何拆分按键

#为什么 222 能有多种解释？

先想象一下老式手机输入法。数字键 2 上有三个字母：

按 1 次 2：输入 a
连续按 2 次 2：输入 b
连续按 3 次 2：输入 c

如果想连续输入两个字母，需要在两个字母之间短暂停顿。例如：

按 2，停顿，再按 22  => ab
按 22，停顿，再按 2  => ba

题目给出的 pressedKeys 只保留按键数字，没有记录停顿位置。所以上面两种操作最后都会被记录成同一个字符串：

222

我们的任务就是推测停顿可能出现在哪里，也就是给连续按键分组。

222 一共有下面四种合法分组：

因此 222 对应 aaa、ab、ba、c，一共有 4 种文本。

要特别注意：

• 每一组只能包含相同的数字。23 不能合成一个字母，因为它们属于不同按键。
• 按键 2 最多连续 3 次表示一个字母，因为它只有 a、b、c 三个字母。
• 所以 2222 不能把四个 2 全部分成一组，只能拆成 2|2|2|2、2|2|22、2|22|2、22|2|2、22|22、2|222、222|2，共 7 种。
• 按键 7 和 9 各有四个字母，因此单组允许包含 1～4 次相同按键。例如 7777 可以整体表示字母 s。

#再看完整示例 22233

"22233" 中，数字发生变化的位置一定是字母之间的分界线：

222 | 33

连续的 2 可以有 4 种拆法：

2 | 2 | 2  -> aaa
2 | 22     -> ab
22 | 2     -> ba
222        -> c

连续的 33 可以有 2 种拆法：

3 | 3  -> dd
33     -> e

两部分可以自由组合，所以总方案数为：

4 × 2 = 8

八种具体文本是：

aaadd、aaae
abdd、abe
badd、bae
cdd、ce

不必真的先切分每一组。使用动态规划扫描整个字符串，就能在数字变化时自然开始新的连续分组。

#1. dp 数组含义

定义：

dp[i] 表示 pressedKeys 的前 i 个字符可以解释成多少种文本

这里的 i 表示前缀长度，不是字符下标：

dp[0]：空前缀
dp[1]：pressedKeys[0]
dp[n]：整个 pressedKeys

最终答案是 dp[pressedKeys.length]。

#2. 确定状态转移方程

计算 dp[i] 时，考虑最后一个字母由多少次连续按键组成。

假设当前位置对应数字 2，最多连续按 3 次：

最后 1 次按键组成一个字母：从 dp[i - 1] 转移
最后 2 次按键组成一个字母：从 dp[i - 2] 转移
最后 3 次按键组成一个字母：从 dp[i - 3] 转移

但只有最后这些按键数字相同时，才能合并成一个字母。例如 "23" 不能把 2 和 3 合并。

数字 7 和 9 最多合并 4 次，其他数字最多合并 3 次。因此统一写成：

limit = 当前数字是 7 或 9 ? 4 : 3

dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[i - length]

其中 length 必须同时满足：

• 1 <= length <= limit；
• 最后的 length 个按键全部相同；
• i - length >= 0，不能越过字符串开头。

每一种 length 都代表最后一个字母使用了不同数量的按键，各种情况互不重复，所以应把方案数相加。

#3. dp 数组如何初始化

dp[0] = 1;

dp[0] = 1 表示空前缀有一种解释方式：什么都不输入。

它是建立后续状态的起点。例如第一个按键单独组成一个字母时：

dp[1] += dp[0]

如果把 dp[0] 设为 0，第一个字符就无法产生任何方案，后续状态也都会是 0。

其余位置先初始化为 0，等待状态转移累加方案数。

#4. 确定遍历顺序

dp[i] 只依赖前面的 dp[i - 1]、dp[i - 2]、dp[i - 3]，最多再依赖 dp[i - 4]。

因此 i 必须从小到大遍历，保证计算 dp[i] 时，它依赖的状态已经得到结果：

i = 1, 2, 3, ..., n

内层从 length = 1 开始向前检查。一旦遇到不同的数字，就立即停止，因为更长的后缀也不可能全部相同。

#5. 示例打印 dp 数组

以 pressedKeys = "22233" 为例。

初始状态：

前缀长度 i   0  1  2  3  4  5
dp[i]         1  0  0  0  0  0

逐步计算：

最终数组为：

dp = [1, 1, 2, 4, 4, 8]

所以答案是 dp[5] = 8。

注意计算 dp[4] 时，最后两个字符是 "23"，数字不同，不能合并。因此最后一个字母只能使用一个按键 3，方案数直接继承 dp[3]。

#不同数字之间的方案数如何关联？

不同数字不能合并成同一个字母，但前一组产生的每一种文本，都可以和后一组产生的每一种文本组合。

以 pressedKeys = "2233" 为例：

22 有 2 种解释：aa、b
33 有 2 种解释：dd、e

两组文本两两组合：

因此总方案数是：

2 × 2 = 4

动态规划没有显式执行乘法，而是通过状态继承和累加得到相同结果。

#第一步：处理 22

dp[0] = 1
dp[1] = dp[0] = 1
dp[2] = dp[1] + dp[0] = 2

此时 dp[2] = 2 已经代表前缀 "22" 的全部解释：aa 和 b。

#第二步：遇到第一个 3

当前前缀是 "223"。末尾的 3 与前面的 2 不同，所以它只能单独组成字母 d：

dp[3] = dp[2] = 2

这里的“继承”表示：给 dp[2] 中的每一种文本都追加一个 d。

aa + d = aad
b  + d = bd

#第三步：遇到第二个 3

当前前缀是 "2233"，最后一个字母有两种取法。

取法一：最后一个字母只使用最后一个 3，即字母 d：

从 dp[3] 转移，共 2 种：
aad + d = aadd
bd  + d = bdd

取法二：最后一个字母使用末尾的 33，即字母 e：

从 dp[2] 转移，共 2 种：
aa + e = aae
b  + e = be

将两种互不重复的情况相加：

dp[4] = dp[3] + dp[2]
      = 2 + 2
      = 4

所以完整的 DP 数组是：

前缀           ""   "2"   "22"   "223"   "2233"
dp              1     1      2       2        4

可以这样理解不同数字之间的关系：

• 数字变化时，新数字不能与上一组合并，因此方案数从前一个完整前缀继承。
• 同一数字继续出现时，可以选择不同长度作为最后一个字母，因此要累加多个前缀状态。
• dp 状态保存的是整个前缀的方案数，所以前面各组的组合结果不会丢失。

#6. 代码实现

var countTexts = function (pressedKeys) {
  // 题目要求方案数对 10^9 + 7 取模
  const MOD = 1_000_000_007;
  const n = pressedKeys.length;

  // dp[i] 表示 pressedKeys 的前 i 个按键能组成多少种文本。
  //
  // 例如 pressedKeys = "2233"：
  // dp[0] 对应 ""
  // dp[1] 对应 "2"
  // dp[2] 对应 "22"
  // dp[3] 对应 "223"
  // dp[4] 对应 "2233"
  const dp = new Array(n + 1).fill(0);

  // 空字符串有一种组成方式：什么都不输入。
  // 它是后续状态转移的起点。
  dp[0] = 1;

  // 外层循环：依次计算每个前缀的方案数。
  //
  // i 表示当前前缀的长度，也是当前要计算的 dp 下标。
  // pressedKeys[i - 1] 才是这个前缀的最后一个按键。
  //
  // 例如 pressedKeys = "2233"：
  // i = 1，计算 "2"    的方案数 dp[1]
  // i = 2，计算 "22"   的方案数 dp[2]
  // i = 3，计算 "223"  的方案数 dp[3]
  // i = 4，计算 "2233" 的方案数 dp[4]
  for (let i = 1; i <= n; i++) {
    // 当前前缀的最后一个按键。
    // 当 i = 4 时，currentKey = pressedKeys[3] = "3"。
    const currentKey = pressedKeys[i - 1];

    // 7 和 9 各对应 4 个字母，一个字母最多使用 4 次按键；
    // 其他按键各对应 3 个字母，一个字母最多使用 3 次按键。
    const limit = currentKey === '7' || currentKey === '9' ? 4 : 3;

    // 内层循环：枚举“最后一个字母”使用了几个连续的相同按键。
    //
    // length = 1：最后一个字母只使用最后 1 个按键，
    //             前面剩余 i - 1 个按键，有 dp[i - 1] 种解释。
    // length = 2：最后一个字母使用最后 2 个按键，
    //             前面剩余 i - 2 个按键，有 dp[i - 2] 种解释。
    // length = 3、4 时同理。
    //
    // length <= limit：一个字母不能超过当前按键对应的字母数量。
    // length <= i：不能向前取超过当前前缀长度的按键。
    for (let length = 1; length <= limit && length <= i; length++) {
      // pressedKeys[i - length] 是本次尝试合并进最后一个字母的按键。
      // 它必须和末尾的 currentKey 相同。
      //
      // 例如 pressedKeys = "2233"、i = 4：
      // length = 1：检查 pressedKeys[3]，即最后一个 "3"，可以组成 d。
      // length = 2：检查 pressedKeys[2]，仍然是 "3"，"33" 可以组成 e。
      // length = 3：检查 pressedKeys[1]，它是 "2"，与 "3" 不同，
      //             所以 "233" 不能表示一个字母，停止继续向前检查。
      if (pressedKeys[i - length] !== currentKey) {
        break;
      }

      // 确定最后一个字母占用 length 个按键后，
      // 前面的 i - length 个按键有 dp[i - length] 种解释。
      // 把这些方案全部追加当前的最后一个字母，就是本次新增的方案数。
      //
      // 例如 pressedKeys = "2233"、i = 4：
      // length = 1：dp[4] += dp[3]，对应在 "aad、bd" 后追加 d；
      // length = 2：dp[4] += dp[2]，对应在 "aa、b" 后追加 e；
      // 最终 dp[4] = dp[3] + dp[2] = 2 + 2 = 4。
      dp[i] = (dp[i] + dp[i - length]) % MOD;
    }
  }

  // dp[n] 表示整个 pressedKeys 可以组成的文本数量
  return dp[n];
};

代码中的内层循环最多执行 4 次，因此虽然写了两层循环，总时间复杂度仍然是线性的。

#正确性说明

对于 pressedKeys 的任意前 i 个字符，最后一个字母一定由末尾连续的 1、2、3 次按键组成；如果当前数字是 7 或 9，还可能由 4 次按键组成。

枚举 length 就完整覆盖了最后一个字母的所有可能情况。确定最后一个字母使用 length 次按键后，前面的 i - length 个按键有 dp[i - length] 种解释方式。

不同的 length 对应不同的最后一个字母边界，方案互不重复，所以将它们相加即可得到 dp[i]。从 dp[0] 开始按前缀长度递推，最终 dp[n] 就是整个字符串的全部解释方案数。

#复杂度分析

• 时间复杂度：O(n)。每个位置最多向前检查 4 个字符。
• 空间复杂度：O(n)，用于保存 dp 数组。

由于每个状态最多只依赖前 4 个状态，还可以使用滚动数组把额外空间优化为 O(1)。不过完整 dp 数组更容易理解和调试，建议先掌握标准写法。

#易错点

• 忘记数字 7 和 9 对应 4 个字母，错误地统一限制为 3 次。
• 只检查连续长度，没有确认这些按键数字相同，例如把 "23" 合并成一个字母。
• 把 dp[0] 初始化为 0，导致所有方案数都无法建立。
• 数字一变化就把答案清零。实际上新分组的第一个按键会从前一个完整前缀继承方案数。
• 内层循环看起来像 O(n²)，但它最多执行 4 次，所以总时间复杂度是 O(n)。
• 忘记在每次累加后取模。

#面试时怎么说

定义 dp[i] 为前 i 个按键可以组成的文本数量。计算 dp[i] 时枚举最后一个字母使用了几次相同按键：普通数字最多 3 次，7 和 9 最多 4 次。如果末尾这些按键相同，就从 dp[i - length] 转移并累加。初始化 dp[0] = 1，按前缀长度正序计算。每个位置最多检查 4 次，因此时间复杂度为 O(n)，空间复杂度为 O(n)。

#自测

1. dp[i] 中的 i 表示字符下标还是前缀长度？
2. 为什么必须初始化 dp[0] = 1？
3. 为什么计算 "2223" 时，最后一个字母只能使用一个按键 3？
4. 为什么内层循环最多执行 4 次？