友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 取余 后返回。
示例 1：
输入：pressedKeys = "22233" 输出：8 解释： Alice 可能发出的文字信息包括： "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。 由于总共有 8 种可能的信息，所以我们返回 8 。
示例 2：
输入：pressedKeys = "222222222222222222222222222222222222" 输出：82876089 解释： 总共有 2082876103 种 Alice 可能发出的文字信息。 由于我们需要将答案对 109 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。
提示：
-
1 <= pressedKeys.length <= 105 -
pressedKeys只包含数字2到9。
思路分析
将字符串按照相同字符进行切割，根据加法原理，每个子串内部是“爬楼梯”：每个按键上面有 3 或 4 个字母，那么按键列表，就可以有 1~3 或 1~4 个按键按出一个字母，这就是爬楼梯：\(f(i) = f(i-1)+f(i-2)+f(i-3)\) 或 \(f(i) = f(i-1)+f(i-2)+f(i-3)+f(i-4)\)；子串之间，根据乘法原理，直接相乘。
-
一刷(暴力破解)
-
一刷(备忘录)
-
一刷(优化备忘录)
-
一刷(动态规划)
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
36
37
/**
* 暴力破解（1/107）->
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-03 11:09:55
*/
public int countTexts(String pressedKeys) {
int mod = 1_000_000_007;
int[] steps = new int[]{3, 3, 3, 3, 3, 4, 3, 4};
int result = 1;
int start = 0;
char[] chars = pressedKeys.toCharArray();
for (int i = 1; i <= chars.length; i++) {
if (i < chars.length && chars[i] == chars[i - 1]) {
continue;
}
result *= dfs(steps[chars[start] - '2'], mod, i - start);
result %= mod;
start = i;
}
return result;
}
private int dfs(int steps, int mod, int length) {
if (length == 0) {
return 1;
}
int result = 0;
for (int i = 1; i <= steps; i++) {
if (i > length) {
break;
}
result += dfs(steps, mod, length - i);
result %= mod;
}
return result % mod;
}
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
36
37
38
39
40
41
42
43
44
45
46
/**
* 暴力破解（1/107）-> 备忘录（29.27%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-03 12:12:05
*/
public int countTexts(String pressedKeys) {
int mod = 1_000_000_007;
int[] steps = new int[]{3, 3, 3, 3, 3, 4, 3, 4};
long result = 1;
int start = 0;
char[] chars = pressedKeys.toCharArray();
long[][] memo = new long[steps.length][chars.length + 1];
for (long[] m : memo) {
Arrays.fill(m, -1);
}
for (int i = 1; i <= chars.length; i++) {
if (i < chars.length && chars[i] == chars[i - 1]) {
continue;
}
int index = chars[start] - '2';
result *= dfs(steps[index], mod, i - start, memo[index]);
result %= mod;
start = i;
}
return (int) result;
}
private long dfs(int steps, int mod, int length, long[] memo) {
if (length == 0) {
return 1L;
}
if (memo[length] >= 0) {
return memo[length];
}
int result = 0;
for (int i = 1; i <= steps; i++) {
if (i > length) {
break;
}
result += dfs(steps, mod, length - i, memo);
result %= mod;
}
return memo[length] = result % mod;
}
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
36
37
38
39
40
41
42
43
44
45
/**
* 暴力破解（1/107）-> 备忘录（29.27%）-> 优化备忘录（60.10%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-03 12:25:05
*/
public int countTexts(String pressedKeys) {
int mod = 1_000_000_007;
int result = 1;
int start = 0;
char[] chars = pressedKeys.toCharArray();
int[] steps = new int[]{3, 4};
int[][] memo = new int[2][chars.length + 1];
for (int[] m : memo) {
Arrays.fill(m, -1);
}
for (int i = 1; i <= chars.length; i++) {
if (i < chars.length && chars[i] == chars[i - 1]) {
continue;
}
int index = (chars[start] == '7' || chars[start] == '9') ? 1 : 0;
result *= dfs(steps[index], mod, i - start, memo[index]);
result %= mod;
start = i;
}
return result;
}
private int dfs(int steps, int mod, int length, int[] memo) {
if (length == 0) {
return 1;
}
if (memo[length] >= 0) {
return memo[length];
}
int result = 0;
for (int i = 1; i <= steps; i++) {
if (i > length) {
break;
}
result += dfs(steps, mod, length - i, memo);
result %= mod;
}
return memo[length] = result;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* 暴力破解（1/107）-> 备忘录（29.27%）-> 优化备忘录（60.10%）-> 动态规划（88.08%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-03 12:25:05
*/
public int countTexts(String pressedKeys) {
int mod = 1_000_000_007;
char[] chars = pressedKeys.toCharArray();
int[] lengths = getLength(chars);
long[][] dp = new long[2][];
dp[0] = new long[lengths[0] + 1];
dp[0][0] = 1;
for (int i = 0; i < dp[0].length; i++) {
for (int j = 1; j <= 3; j++) {
if (i + j >= dp[0].length) {
break;
}
dp[0][i + j] += dp[0][i];
dp[0][i + j] %= mod;
}
}
dp[1] = new long[lengths[1] + 1];
dp[1][0] = 1;
for (int i = 0; i < dp[1].length; i++) {
for (int j = 1; j <= 4; j++) {
if (i + j >= dp[1].length) {
break;
}
dp[1][i + j] += dp[1][i];
dp[1][i + j] %= mod;
}
}
long result = 1;
int start = 0;
for (int i = 1; i <= chars.length; i++) {
if (i < chars.length && chars[i] == chars[i - 1]) {
continue;
}
int index = (chars[start] == '7' || chars[start] == '9') ? 1 : 0;
result *= dp[index][i - start];
result %= mod;
start = i;
}
return (int) result;
}
private int[] getLength(char[] chars) {
int[] result = new int[2];
int start = 0;
for (int i = 1; i <= chars.length; i++) {
if (i < chars.length && chars[i] == chars[i - 1]) {
continue;
}
int index = (chars[start] == '7' || chars[start] == '9') ? 1 : 0;
result[index] = Math.max(result[index], i - start);
start = i;
}
return result;
}