leetcode2266.统计打字方案数

2266. 统计打字方案数

中等（动态规划）

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

img

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

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

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

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

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

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

示例 1：

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

示例 2：

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

代码一：递归

超出内存限制 98 / 107 个通过的测试用例

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
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9+7
        dic = [0, 3, 3, 3, 3, 3, 4, 3, 4]

        @cache
        def func1(s):
            if not s:
                return 1  
            count = 1
            for i in range(1, len(s)):
                if s[i] == s[0]:
                    count += 1
                else:
                    break
            a = int(s[0])
            ans = 0
            if count < 4:
                for i in range(1, count + 1):
                    ans = (ans + func1(s[i:])) % MOD
                return ans
            if dic[a-1] == 4:  
                for i in range(1, 5):
                    ans = (ans + func1(s[i:])) % MOD
                return ans
            for i in range(1, 4):
                ans = (ans + func1(s[i:])) % MOD
            return ans

        return func1(pressedKeys)

代码二：动态规划（dp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9+7
        dic = [0, 3, 3, 3, 3, 3, 4, 3, 4]
        n = len(pressedKeys)
        dp = [0]*(n+1) 
        #dp 是一个动态规划数组，其中 dp[i] 表示前 i 个按键可以形成的不同文本消息数量。初始化 dp[0] = 1，表示空字符串有一种方式。
        dp[0] = 1
        for i in range(1, n+1):
            pos = int(pressedKeys[i-1])
            k = dic[pos-1]
            count = 0
            for j in range(1,k+1):
                #内层循环 j 遍历从 1 到 k，检查当前按键是否可以和前 j 个按键形成有效的字符组合。
                if i-j >= 0 and pressedKeys[i-1] == pressedKeys[i - j]:
                    #当前按键和前 j 个按键可以形成一个有效的字符组合。
                    count = (count + dp[i - j]) % MOD
                    continue
                break
            dp[i] = count
        return dp[n]

例子

假设 pressedKeys = "22233":

  • 对于 i=1，pressedKeys[0] 是 ‘2’，它可以形成 ‘a’，所以 dp[1] = 1。
  • 对于 i=2，pressedKeys[1] 也是 ‘2’，它可以形成 ‘aa’ 或 ‘b’，所以 dp[2] = 2。
  • 对于 i=3，pressedKeys[2] 依然是 ‘2’，它可以形成 ‘aaa’、’ab’、’ba’，所以 dp[3] = 4。
  • 对于 i=4，pressedKeys[3] 是 ‘3’，它可以形成 ‘aaac’、’aab’、’abc’、’bbc’，所以 dp[4] = 4。
  • 对于 i=5，pressedKeys[4] 也是 ‘3’，它可以形成 ‘aaacc’、’aabb’、’abcc’、’bbcc’，所以 dp[5] = 8。