Medium

题目描述

Alice 正在用她的手机给 Bob 发短信。数字到字母的映射如下图所示。

为了添加一个字母，Alice 需要按对应数字键 i 次，其中 i 是该字母在按键上的位置。

  • 例如，要添加字母 ’s’，Alice 需要按 ‘7’ 四次。类似地，要添加字母 ‘k’，Alice 需要按 ‘5’ 两次。
  • 注意数字 ‘0’ 和 ‘1’ 不映射到任何字母，所以 Alice 不会使用它们。

但是，由于传输错误，Bob 没有收到 Alice 的短信，而是收到了一串按键记录。

  • 例如，当 Alice 发送消息 “bob” 时，Bob 收到的字符串是 “2266622”。

给定一个字符串 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
解释：
Alice 可能发送的文本消息有 2082876103 种。
因为需要返回对 10^9 + 7 取模的结果，所以返回 2082876103 % (10^9 + 7) = 82876089。

约束条件：

  • 1 <= pressedKeys.length <= 10^5
  • pressedKeys 只包含数字 ‘2’ 到 ‘9’

提示：

  • 对于由相同数字组成的子串，如何计算它最初可能代表的文本数量？
  • 动态规划如何帮助我们计算所需的答案？

解题思路

这是一道经典的动态规划问题，核心思想是将问题分解为连续相同数字段的组合问题。

首先，我们需要理解手机按键映射：数字2-6对应3个字母，数字7和9对应4个字母，数字8对应3个字母。这意味着对于连续的相同数字，最多可以组成3或4个字母的组合。

解题思路：

  1. 分段处理：将输入字符串按照相同数字分组，每组内部计算可能的文本组合数
  2. 动态规划：对于长度为n的相同数字段，定义dp[i]为前i个数字的组合数
    • 状态转移：dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + (dp[i-4] if 数字是7或9)
    • 这是因为每次可以选择1-3个相同数字组成一个字母（对于7和9可以选择4个）
  3. 乘法原理：各段的组合数相乘得到最终答案

优化点：

  • 预计算斐波那契类型的数列，避免重复计算
  • 使用取模运算防止整数溢出
  • 一次遍历完成分段和计算

代码实现

class Solution {
public:
    int countTexts(string pressedKeys) {
        const int MOD = 1e9 + 7;
        int n = pressedKeys.length();
        
        // 预计算dp数组，dp[i]表示长度为i的相同数字串的组合数
        vector<long long> dp3(n + 1), dp4(n + 1);
        dp3[0] = dp4[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp3[i] = dp3[i-1];
            if (i >= 2) dp3[i] = (dp3[i] + dp3[i-2]) % MOD;
            if (i >= 3) dp3[i] = (dp3[i] + dp3[i-3]) % MOD;
            
            dp4[i] = dp4[i-1];
            if (i >= 2) dp4[i] = (dp4[i] + dp4[i-2]) % MOD;
            if (i >= 3) dp4[i] = (dp4[i] + dp4[i-3]) % MOD;
            if (i >= 4) dp4[i] = (dp4[i] + dp4[i-4]) % MOD;
        }
        
        long long result = 1;
        int i = 0;
        
        while (i < n) {
            char digit = pressedKeys[i];
            int count = 0;
            
            // 统计连续相同数字的个数
            while (i < n && pressedKeys[i] == digit) {
                count++;
                i++;
            }
            
            // 根据数字类型选择对应的dp数组
            if (digit == '7' || digit == '9') {
                result = (result * dp4[count]) % MOD;
            } else {
                result = (result * dp3[count]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9 + 7
        n = len(pressedKeys)
        
        # 预计算dp数组
        dp3 = [0] * (n + 1)
        dp4 = [0] * (n + 1)
        dp3[0] = dp4[0] = 1
        
        for i in range(1, n + 1):
            dp3[i] = dp3[i-1]
            if i >= 2:
                dp3[i] = (dp3[i] + dp3[i-2]) % MOD
            if i >= 3:
                dp3[i] = (dp3[i] + dp3[i-3]) % MOD
                
            dp4[i] = dp4[i-1]
            if i >= 2:
                dp4[i] = (dp4[i] + dp4[i-2]) % MOD
            if i >= 3:
                dp4[i] = (dp4[i] + dp4[i-3]) % MOD
            if i >= 4:
                dp4[i] = (dp4[i] + dp4[i-4]) % MOD
        
        result = 1
        i = 0
        
        while i < n:
            digit = pressedKeys[i]
            count = 0
            
            # 统计连续相同数字的个数
            while i < n and pressedKeys[i] == digit:
                count += 1
                i += 1
            
            # 根据数字类型选择对应的dp数组
            if digit in '79':
                result = (result * dp4[count]) % MOD
            else:
                result = (result * dp3[count]) % MOD
        
        return result

public class Solution {
    public int CountTexts(string pressedKeys) {
        const int MOD = 1000000007;
        int n = pressedKeys.Length;
        
        // 预计算dp数组
        long[] dp3 = new long[n + 1];
        long[] dp4 = new long[n + 1];
        dp3[0] = dp4[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp3[i] = dp3[i-1];
            if (i >= 2) dp3[i] = (dp3[i] + dp3[i-2]) % MOD;
            if (i >= 3) dp3[i] = (dp3[i] + dp3[i-3]) % MOD;
            
            dp4[i] = dp4[i-1];
            if (i >= 2) dp4[i] = (dp4[i] + dp4[i-2]) % MOD;
            if (i >= 3) dp4[i] = (dp4[i] + dp4[i-3]) % MOD;
            if (i >= 4) dp4[i] = (dp4[i] + dp4[i-4]) % MOD;
        }
        
        long result = 1;
        int idx = 0;
        
        while (idx < n) {
            char digit = pressedKeys[idx];
            int count = 0;
            
            // 统计连续相同数字的个数
            while (idx < n && pressedKeys[idx] == digit) {
                count++;
                idx++;
            }
            
            // 根据数字类型选择对应的dp数组
            if (digit == '7' || digit == '9') {
                result = (result * dp4[count]) % MOD;
            } else {
                result = (result * dp3[count]) % MOD;
            }
        }
        
        return (int)result;
    }
}

var countTexts = function(pressedKeys) {
    const MOD = 1e9 + 7;
    const n = pressedKeys.length;
    
    // 预计算dp数组
    const dp3 = new Array(n + 1).fill(0);
    const dp4 = new Array(n + 1).fill(0);
    dp3[0] = dp4[0] = 1;
    
    for (let i = 1; i <= n; i++) {
        dp3[i] = dp3[i-1];
        if (i >= 2) dp3[i] = (dp3[i] + dp3[i-2]) % MOD;
        if (i >= 3) dp3[i] = (dp3[i] + dp3[i-3]) % MOD;
        
        dp4[i] = dp4[i-1];
        if (i >= 2) dp4[i] = (dp4[i] + dp4[i-2]) % MOD;
        if (i >= 3) dp4[i] = (dp4[i] + dp4[i-3]) % MOD;
        if (i >= 4) dp4[i] = (dp4[i] + dp4[i-4]) % MOD;
    }
    
    let result = 1;
    let i = 0;
    
    while (i < n) {
        const digit = pressedKeys[i];
        let count = 0;
        
        // 统计连续相同数字的个数
        while (i < n && pressedKeys[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是输入字符串的长度。时间复杂度为 O(n) 是因为需要预计算 dp 数组和遍历一次字符串。空间复杂度为 O(n) 是因为需要存储两个长度为 n+1 的 dp 数组。

相关题目