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

题目形貌

题解思路

我们利用逆向思维发现如果连续按存在三个字母的按键，末了一个按键表现的字母可以是某个字母连续出现一次、两次、三次这三种环境的方案数之和
我们发现连续按存在三个字母的按键，当连续按i次时其方案数f = f[i - 1] + f[i - 2] + f[i - 3]
此中f[i - 1]表现末了一个按键表现的末了一个字母连续出现一次的方案数
f[i - 2]表现末了一个按键表现的末了一个字母连续出现l两次的方案数
f[i - 3]表现末了一个按键表现的末了一个字母连续出现三次的方案数
雷同的按存在四个字母的按键，当连续按i次时其方案数f = f[i - 1] + f[i - 2] + f[i - 3] + f[i - 4]
然后我们只需要计算全部连续的字母其出现了反复，然后将其方案数相乘就是终极的结果
题解代码

1. func countTexts(pressedKeys string) int {
2.     const mod = 1000000007
3.     n := len(pressedKeys)
4.     f3, f4 := make([]int, 0, n + 1), make([]int, 0, n + 1)
5.     f3 = append(f3, 1, 1, 2, 4)
6.     f4 = append(f4, 1, 1, 2, 4)
8.     for i := 4; i <= n; i++ {
9.         f3 = append(f3, (f3[i - 1] + f3[i - 2] + f3[i - 3]) % mod)
10.         f4 = append(f4, (f4[i - 1] + f4[i - 2] + f4[i - 3] + f4[i - 4]) % mod)
11.     }
13.     ans, cnt := 1, 0
14.     for i := 0; i < n; i++ {
15.         cnt++
16.         if i == n - 1 || pressedKeys[i] != pressedKeys[i + 1] {
17.             if pressedKeys[i] == '7' || pressedKeys[i] == '9' {
18.                 ans = ans * f4[cnt] % mod
19.             } else {
20.                 ans = ans * f3[cnt] % mod
21.             }
22.             cnt = 0
23.         }
24.     }
26.     return ans
27. }

复制代码

题目链接

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。