What is the main pattern in Count Number of Texts?

The main pattern is state transition dynamic programming applied to contiguous blocks of identical digits.

How do you handle keys with 3 or 4 letters?

Use the maximum number of presses allowed per key in your DP calculation to sum valid text combinations.

Why use modulo 10^9 + 7 in this problem?

Because the number of possible texts can grow very large, and modulo prevents integer overflow.

Can this approach work for pressedKeys up to length 10^5?

Yes, the DP with block optimization ensures linear time processing suitable for large inputs.

Is it necessary to generate all text messages?

No, only counting the number of possible messages is needed; generating each message is inefficient for long sequences.

#2266

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计打字方案数

Alice 在给 Bob 用手机打字。数字到字母的对应如下图所示。为了打出一个字母，Alice 需要按对应字母 i 次， i 是该字母在这个按键上所处的位置。比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' …

哈希表数学字符串动态规划

题目描述

Alice 在给 Bob 用手机打字。数字到字母的对应如下图所示。

为了打出一个字母，Alice 需要按对应字母 i 次，i 是该字母在这个按键上所处的位置。

比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' 。
注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不使用它们。

但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。

比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。

给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。

由于答案可能很大，将它对 10⁹ + 7 取余后返回。

示例 1：

输入：pressedKeys = "22233"
输出：8
解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。

示例 2：

输入：pressedKeys = "222222222222222222222222222222222222"
输出：82876089
解释：
总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 10⁹ + 7 取余，所以我们返回 2082876103 % (10⁹ + 7) = 82876089 。

提示：

1 <= pressedKeys.length <= 10⁵
pressedKeys 只包含数字 '2' 到 '9' 。

lightbulb

解题思路

方法一：分组 + 动态规划

根据题目描述，对于字符串 $\textit{pressedKeys}$ 中连续的相同字符，可以将其分为一组，然后分别计算每组的方案数，最后将所有组的方案数相乘即可。

问题的关键在于如何计算每组的方案数。

如果一组字符为 '7' 或 '9'，我们可以分别将该组的末尾 $1$ , $2$ , $3$ , $4$ 个字符视为一个字母，然后将该组字符规模缩小，转化为规模更小的子问题。

同样地，如果一组字符为 '2', '3', '4', '5', '6', '8'，我们可以将该组的末尾 $1$ , $2$ , $3$ 个字符视为一个字母，然后将该组字符规模缩小，转化为规模更小的子问题。

因此，我们定义 $f[i]$ 表示长度为 $i$ 的连续相同字符，且字符不为 '7' 或 '9' 的方案数，定义 $g[i]$ 表示长度为 $i$ 的连续相同字符，且字符为 '7' 或 '9' 的方案数。

初始时 $f[0] = f[1] = 1$ , $f[2] = 2$ , $f[3] = 4$ , $g[0] = g[1] = 1$ , $g[2] = 2$ , $g[3] = 4$ 。

对于 $i \ge 4$ ，有：

\begin{aligned} f[i] & = f[i-1] + f[i-2] + f[i-3] \\ g[i] & = g[i-1] + g[i-2] + g[i-3] + g[i-4] \end{aligned}

最后，我们遍历 $\textit{pressedKeys}$ ，将连续相同字符分组，然后计算每组的方案数，最后将所有组的方案数相乘即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $\textit{pressedKeys}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

mod = 10**9 + 7
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(100000):
    f.append((f[-1] + f[-2] + f[-3]) % mod)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)


class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for c, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if c in "79" else f[m]) % mod
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the length of pressedKeys, as each character is processed once in DP. Space complexity is O(n) for storing DP results for each position, optimized to O(1) if only the last few DP states are kept due to the maxPress limit per key.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect a DP solution based on repeated digits substrings
question_mark
Check if candidate handles different key lengths (3 or 4 letters per digit)
question_mark
Look for modulo arithmetic to prevent integer overflow

warning

常见陷阱

外企场景

error
Miscounting combinations for blocks exceeding key letter limits
error
Ignoring modulo arithmetic and risking overflow
error
Treating each digit independently instead of considering contiguous blocks

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the mapping to allow variable letters per key dynamically
arrow_right_alt
Count texts with additional constraints like maximum word length
arrow_right_alt
Compute all possible message strings explicitly for small pressedKeys

help

常见问题

外企场景

继续练习

#2262 字符串的总引力 #3335 字符串转换后的长度 I #3337 字符串转换后的长度 II