LeetCode讲解篇之2266. 统计打字方案数

题目描述

题解思路

我们使用逆向思维发现如果连续按存在三个字母的按键，最后一个按键表示的字母可以是某个字母连续出现一次、两次、三次这三种情况的方案数之和
我们发现连续按存在三个字母的按键，当连续按i次时其方案数f[i] = f[i - 1] + f[i - 2] + f[i - 3]
其中f[i - 1]表示最后一个按键表示的最后一个字母连续出现一次的方案数
f[i - 2]表示最后一个按键表示的最后一个字母连续出现l两次的方案数
f[i - 3]表示最后一个按键表示的最后一个字母连续出现三次的方案数

类似的按存在四个字母的按键，当连续按i次时其方案数f[i] = f[i - 1] + f[i - 2] + f[i - 3] + f[i - 4]

然后我们只需要计算所有连续的字母其出现了几次，然后将其方案数相乘就是最终的结果

题解代码

func countTexts(pressedKeys string) int {
    const mod = 1000000007
    n := len(pressedKeys)
    f3, f4 := make([]int, 0, n + 1), make([]int, 0, n + 1)
    f3 = append(f3, 1, 1, 2, 4)
    f4 = append(f4, 1, 1, 2, 4)

    for i := 4; i <= n; i++ {
        f3 = append(f3, (f3[i - 1] + f3[i - 2] + f3[i - 3]) % mod)
        f4 = append(f4, (f4[i - 1] + f4[i - 2] + f4[i - 3] + f4[i - 4]) % mod)
    }

    ans, cnt := 1, 0
    for i := 0; i < n; i++ {
        cnt++
        if i == n - 1 || pressedKeys[i] != pressedKeys[i + 1] {
            if pressedKeys[i] == '7' || pressedKeys[i] == '9' {
                ans = ans * f4[cnt] % mod
            } else {
                ans = ans * f3[cnt] % mod
            }
            cnt = 0
        }
    }

    return ans
}

题目链接

https://leetcode.cn/problems/count-number-of-texts/description/