alice在用手机给bob发送信息时，使用的按键和字母的对应关系如下图所示。
为了输入一个字母，Alice需要按对应按键的次数，等于该字母在按键上的位置。例如，要输入字母 ‘s’，Alice需要按 ‘7’ 四次；要输入字母 ‘k’，Alice需要按 ‘5’ 两次。
需要注意的是，数字 ‘0’ 和 ‘1’ 没有对应的字母，因此Alice不会使用它们。
然而，由于传输错误，Bob收到的不是Alice发送的字母信息，而是按键的字符串信息。例如，Alice发送的信息为 “bob”，Bob会收到字符串 “2266622”。
立即学习“go语言免费学习笔记（深入）”；
现在给你一个字符串 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
怪兽AI数字人
数字人短视频创作，数字人直播，实时驱动数字人
44 查看详情
解释：
总共有2082876103种Alice可能发送的文字信息。
由于需要对10^9 + 7取模，返回2082876103 % (10^9 + 7) = 82876089。
提示：
1 <= pressedKeys.length <= 10^5pressedKeys 只包含数字 ‘2’ 到 ‘9’。
解题思路：
这个问题可以转化为爬楼梯问题，具体情况如下：
A. 如果连续两个字符相同，可以爬1步或2步。
B. 如果连续三个字符相同，可以爬1步、2步或3步。
C. 如果连续四个或更多字符相同，且是7或9，可以爬1步、2步、3步或4步。
D. 如果字符不相同，只能爬一步。
这是一个类似于斐波那契数列的问题。
可以通过动态规划来解决。
代码实现：
function countTexts(pressedKeys) { const dp = new Array(pressedKeys.length + 1).fill(0); dp[0] = 1; for (let i = 1; i = 4 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3] && pressedKeys[i-1] === pressedKeys[i-4] && (pressedKeys[i-1] === '7' || pressedKeys[i-1] === '9')) { tmp = (dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]) % 1000000007; } else if (i >= 3 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3]) { tmp = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007; } else if (i >= 2 && pressedKeys[i-1] === pressedKeys[i-2]) { tmp = (dp[i-1] + dp[i-2]) % 1000000007; } else { tmp = dp[i-1]; } dp[i] = tmp; } return dp[pressedKeys.length];}
目前这个实现的空间复杂度是O(n)，但可以进一步优化到O(1)，因为我们只需要使用到dp数组中的四个变量。因此，可以使用一个长度为4的数组来优化空间复杂度。
优化后的代码：
function countTexts(pressedKeys) { const dp = [1, 1, 1, 1]; for (let i = 1; i = 4 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3] && pressedKeys[i-1] === pressedKeys[i-4] && (pressedKeys[i-1] === '7' || pressedKeys[i-1] === '9')) { tmp = (dp[3] + dp[2] + dp[1] + dp[0]) % 1000000007; } else if (i >= 3 && pressedKeys[i-1] === pressedKeys[i-2] && pressedKeys[i-1] === pressedKeys[i-3]) { tmp = (dp[3] + dp[2] + dp[1]) % 1000000007; } else if (i >= 2 && pressedKeys[i-1] === pressedKeys[i-2]) { tmp = (dp[3] + dp[2]) % 1000000007; } else { tmp = dp[3]; } dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = dp[3]; dp[3] = tmp; } return dp[3];}
以上就是golang 刷leetcode：统计打字方案数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/460518.html
微信扫一扫 
支付宝扫一扫 
