题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一串打字的按键记录（手机九宫格），请给出这些打字记录可以显现出来的字符串方案个数。

思路分享

  • 如果只是但看一种数字串的组合方案，就很容易发现这是根据字母个数固定的（3或4）。对每一段连续数字，都可以用 dfs 遍一下。为什么不会因重复超时？因为即使是不同种数字，只要数量相同和字母个数相同，那么组合出的方案也相同。

  • 本题最重要的是学到了用 groupby 函数可以把列表中的一段段同种数字整合成一个个值与对应的迭代器，注意，迭代器一旦使用就不可逆，所以要么就使用一次（下面就是只是用了一次量长度），要么就保存到另一个变量使用。

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9 + 7
        
        @cache
        def dfs(remaining, is_special):
            """统一的DFS函数"""
            if remaining == 0:
                return 1
            if remaining < 0:
                return 0
            
            total = 0
            max_step = 4 if is_special else 3
            for step in range(1, max_step + 1):
                total = (total + dfs(remaining - step, is_special)) % MOD
            return total
        
        result = 1
        for ch, group in groupby(pressedKeys):
            length = len(list(group))
            is_special = (ch in "79")
            result = (result * dfs(length, is_special)) % MOD
        
        return result
        
        # MOD = 1_000_000_007
        # # 下面分别是有三个字母和四个字母按 0、1、2、3 的可能次数
        # f = [1, 1, 2, 4]
        # g = [1, 1, 2, 4]

        # for _ in range(100_002):
        #     f.append((f[-1]+f[-2]+f[-3])%MOD)
        #     g.append((g[-1]+g[-2]+g[-3]+g[-4])%MOD)
        
        # res = 1
        # for i, s in groupby(pressedKeys):
        #     n = len(list(s))
        #     res =  res * (g[n] if i in "79" else f[n]) % MOD
        # return res