力扣周赛292--第三题

2266. 统计打字方案数

题目

Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。

为了 打出 一个字母,Alice 需要 对应字母 i 次,i 是该字母在这个按键上所处的位置。

  • 比方说,为了按出字母 's' ,Alice 需要按 '7' 四次。类似的, Alice 需要按 '5' 两次得到字母 'k'
  • 注意,数字 '0''1' 不映射到任何字母,所以 Alice 使用它们。

但是,由于传输的错误,Bob 没有收到 Alice 打字的字母信息,反而收到了 按键的字符串信息

  • 比方说,Alice 发出的信息为 "bob" ,Bob 将收到字符串 "2266622"

给你一个字符串 pressedKeys ,表示 Bob 收到的字符串,请你返回 Alice 总共可能发出多少种文字信息

由于答案可能很大,将它对 109 + 7 取余 后返回。

示例 1:

输入:pressedKeys = "22233"  
输出:8  
解释:  
Alice 可能发出的文字信息包括:  
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。  
由于总共有 8 种可能的信息,所以我们返回 8 。  

示例 2:

输入:pressedKeys = "222222222222222222222222222222222222"  
输出:82876089  
解释:  
总共有 2082876103 种 Alice 可能发出的文字信息。  
由于我们需要将答案对 109 + 7 取余,所以我们返回 2082876103 % (109 + 7) = 82876089 。  

提示:

  • 1 <= pressedKeys.length <= 105
  • pressedKeys 只包含数字 '2''9'

思路

这题标的是中等题,个人觉得解题方法有点取巧,怎么取巧尼,因为重复的数最多4个,我完全可以嵌套3层if来处理,当然我也是这么干的。只要遍历一遍就可以了。

在遍历到索引i时,有如下情况:

  1. 当前数字不和前面的组合,自己单独成一个新的

    索引i的种数 = 索引i-1的种数

  2. 当前数字与前一个相等,那么该数字的组合就有两种情况

    • 直接和前一个数字凑一起

      索引i的种数=索引i-2的种数

    • 索引i的数字和索引i-2的数字也相等,这也有2种情况

      • 把索引i,i-1,i-2都凑一起

        索引i的种数=索引i-3的种数

      • 索引i是7或者9,最多可以连续4个,把索引i,i-1,i-2,i-3都凑一起

        索引i的种数=索引i-4的种数

同时,为了保证数据没有超过int的最大值,这里对于每一次的结果都对109+7取余

代码

Java:

java
  • 01
  • 02
  • 03
  • 04
  • 05
  • 06
  • 07
  • 08
  • 09
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
class Solution { public int countTexts(String pressedKeys) { int[] cnts = new int[pressedKeys.length() + 1]; cnts[0] = 1; cnts[1] = 1; int mod = 1000000007; for (int i = 1; i < pressedKeys.length(); i++) { cnts[i + 1] = cnts[i]; if (pressdKeys.charAt(i) == pressedKeys.charAt(i - 1)) { cnts[i + 1] += cnts[i - 1]; cnts[i + 1] %= mod; if (i > 1 && pressedKeys.charAt(i) == pressedKeys.charAt(i - 2)) { cnts[i + 1] += cnts[i - 2]; cnts[i + 1] %= mod; if (i > 2 && pressedKeys.charAt(i) == pressedKeys.charAt(i - 3) && (pressedKeys.charAt(i) == '7' || pressedKeys.charAt(i) == ' cnts[i + 1] += cnts[i - 3]; cnts[i + 1] %= mod; } } } } return cnts[pressedKeys.length()]; } }