2266. 统计打字方案数

难度

• Easy
• Medium
• Hard

思路

1. 对于不同的数字，其可能性是不重叠的，对于相同的数字，需要考虑它是单独按的，还是连续按的。
2. 那么，可以先把字符串分割为许多连续子串，每个字串内的字符是相同的。
3. 总的方案数应当是每个子串的方案数相乘。
4. 考虑一个连续数字的串对应的方案数。对于一个新按下的数字，有若干种可能性：
   1. 单独按下
   2. 与前一个一起连续按下
   3. 与前两个一起连续按下
   4. ……
5. 能连续按多少次，取决于一个数字最大对应几个字母（隐含）。
6. 换句话说，当前新按下的数字的状态，依赖于前几个数字的状态，那么可以用 DP 。

代码

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        nums = [0, 0, 3, 3, 3, 3, 3, 4, 3, 4] # 每个数字对应有几个字母
        n = len(pressedKeys)
        ans = 1
        MOD = 1000000007
        # 分割子串为相同字符的连续字符串
        start = 0
        keys = []
        for i in range(n + 1):
            if i == n or pressedKeys[i] != pressedKeys[start]:
                keys.append(pressedKeys[start:i])
                start = i
        # 分别处理每个子串
        for key in keys:
            m = len(key)
            dp = [0] * (m + 1)
            dp[0] = dp[1] = 1
            for i in range(2, m + 1):
                j = i - 1
                while j >= 0 and i - j <= nums[int(key[0])]:
                    dp[i] = (dp[i] + dp[j]) % MOD
                    j -= 1
            ans = (ans * dp[m]) % MOD
        return ans