【LetMeFly】2266.統計打字方案數：排列組合

力扣題目鏈接：https://leetcode.cn/problems/count-number-of-texts/

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'?。

解題方法：排列組合

按鍵2可以按1/2/3次，那么n次連續的按鍵2共有多少種拼寫可能？

使用數組dp3，其中dp3[n]代表連續按2鍵n次有多少種拼寫方案。我們考慮最后一個按出來的字母：

1. 第n次按2可以在按了n - 1次的基礎上再按1次（得到a）
2. 第n次按2可以在按了n - 2次的基礎上連續按2次（得到b）
3. 第n次按2可以在按了n - 3次的基礎上連續按3次（得到c）

因此dp3[n] = (dp3[n - 1] + dp3[n - 2] + dp3[n - 3]) % mod

和按鍵2一樣，按鍵3/4/5/6/8同樣適用于dp3數組；而按鍵7和按鍵9最多可以連按4次，因此可以計算dp4數組：

dp4[n] = (dp4[n - 1] + dp4[n - 2] + dp4[n - 3] + dp4[n - 4]) % mod

給你一個按鍵字符串如22233，我們可以通過一次遍歷很輕松地得到“連按了3次2，又連按了2次3”這一信息。

連按3次2可以有dp3[3]種方案，連按2次3可以有dp3[2]種方案，因此依據乘法原理，總計有dp3[3] * dp3[2]種方案。

• 時間復雜度$O(len(pressedKeys))$
• 空間復雜度$O(len(pressedKeys))$

AC代碼

C++

const int mod = 1e9 + 7;
int dp3[100001], dp4[100001];
int init = []() {dp3[0] = dp4[0] = 1;dp3[1] = dp4[1] = 1;dp3[2] = dp4[2] = 2;dp3[3] = dp4[3] = 4;for (int i = 4; i <= 100000; i++) {dp3[i] = ((dp3[i- 1] + dp3[i - 2]) % mod + dp3[i - 3]) % mod;dp4[i] = (((dp4[i - 1] + dp4[i - 2]) % mod + dp4[i - 3]) % mod + dp4[i - 4]) % mod;}return 0;
}();class Solution {
public:int countTexts(string& pressedKeys) {long long ans = 1;int cnt = 0;for (int i = 0; i < pressedKeys.size(); i++) {cnt++;if (i == pressedKeys.size() - 1 || pressedKeys[i] != pressedKeys[i + 1]) {ans = ans * (pressedKeys[i] == '7' || pressedKeys[i] == '9' ? dp4[cnt] : dp3[cnt]) % mod;cnt = 0;}}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-01-19 14:06:29
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-19 14:16:32
'''
MOD = 1000000007
dp3 = [1, 1, 2, 4] + [0] * 100000
dp4 = [1, 1, 2, 4] + [0] * 100000
for i in range(4, 100001):dp3[i] = (dp3[i - 1] + dp3[i - 2] + dp3[i - 3]) % MODdp4[i] = (dp4[i - 1] + dp4[i - 2] + dp4[i - 3] + dp4[i - 4]) % MODclass Solution:def countTexts(self, pressedKeys: str) -> int:ans = 1cnt = 0for i in range(len(pressedKeys)):cnt += 1if i == len(pressedKeys) - 1 or pressedKeys[i] != pressedKeys[i + 1]:ans = ans * (dp4[cnt] if pressedKeys[i] == '7' or pressedKeys[i] == '9' else dp3[cnt]) % MODcnt = 0return ans

Java

/** @Author: LetMeFly* @Date: 2025-01-19 14:16:55* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-19 14:19:48*/
class Solution {private static final int mod = 1000000007;private static final int[] dp3 = new int[100001];private static final int[] dp4 = new int[100001];static {dp3[0] = dp4[0] = 1;dp3[1] = dp4[1] = 1;dp3[2] = dp4[2] = 2;dp3[3] = dp4[3] = 4;for (int i = 4; i <= 100000; i++) {dp3[i] = ((dp3[i- 1] + dp3[i - 2]) % mod + dp3[i - 3]) % mod;dp4[i] = (((dp4[i - 1] + dp4[i - 2]) % mod + dp4[i - 3]) % mod + dp4[i - 4]) % mod;}}public int countTexts(String pressedKeys) {long ans = 1;int cnt = 0;for (int i = 0; i < pressedKeys.length(); i++) {cnt++;if (i == pressedKeys.length() - 1 || pressedKeys.charAt(i) != pressedKeys.charAt(i + 1)) {ans = ans * (pressedKeys.charAt(i) == '7' || pressedKeys.charAt(i) == '9' ? dp4[cnt] : dp3[cnt]) % mod;cnt = 0;}}return (int)ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-19 14:21:47* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-19 14:55:32*/
package mainconst mod int = 1000000007
var dp3 = [100001]int{1, 1, 2, 4}
var dp4 = dp3func init() {for i := 4; i <= 100000; i++ {dp3[i] = ((dp3[i- 1] + dp3[i - 2]) % mod + dp3[i - 3]) % mod;dp4[i] = (((dp4[i - 1] + dp4[i - 2]) % mod + dp4[i - 3]) % mod + dp4[i - 4]) % mod;}
}func countTexts(pressedKeys string) int {ans := int64(1)cnt := 0for i, c := range pressedKeys {cnt++if i == len(pressedKeys) - 1 || byte(c) != pressedKeys[i + 1] {if c == '7' || c == '9' {ans = ans * int64(dp4[cnt]) % int64(mod)} else {ans = ans * int64(dp3[cnt]) % int64(mod)}cnt = 0}}return int(ans)
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145243054