Medium

题目描述

你截获了一条用数字编码的秘密消息。该消息通过以下映射进行解码：

“1” -> ‘A’ “2” -> ‘B’ … “25” -> ‘Y’ “26” -> ‘Z’

然而，在解码消息时，你意识到有很多不同的方式可以解码消息，因为一些编码包含在其他编码中（“2” 和 “5” 与 “25”）。

例如，“11106” 可以解码为：

  • “AAJF”，分组为 (1, 1, 10, 6)
  • “KJF”，分组为 (11, 10, 6)
  • 分组 (1, 11, 06) 是无效的，因为 “06” 不是有效编码（只有 “6” 是有效的）

注意：可能存在无法解码的字符串。

给定一个只包含数字的字符串 s，返回解码它的方法数。如果整个字符串无法以任何有效方式解码，返回 0。

测试用例保证答案能够用 32 位整数表示。

示例 1：

输入：s = "12"
输出：2
解释："12" 可以解码为 "AB"（1 2）或 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释："226" 可以解码为 "BZ"（2 26）、"VF"（22 6）或 "BBF"（2 2 6）。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F"，因为前导零（"6" 与 "06" 不同）。在这种情况下，字符串不是有效编码，返回 0。

约束条件：

  • 1 <= s.length <= 100
  • s 只包含数字，可能包含前导零

解题思路

这是一个典型的动态规划问题。我们需要考虑每个位置的字符可以单独解码，或者与前一个字符组合解码。

核心思路：

对于字符串的每个位置 i，我们可以：

  1. 单独解码当前字符（如果它不是 ‘0’）
  2. 与前一个字符组合解码（如果组合后的数字在 10-26 范围内）

状态定义：

  • dp[i] 表示前 i 个字符的解码方法数
  • dp[0] = 1（空字符串有一种解码方法）

状态转移：

  • 如果 s[i-1] != '0'，则可以单独解码：dp[i] += dp[i-1]
  • 如果 s[i-2:i] 在 “10” 到 “26” 范围内，则可以组合解码：dp[i] += dp[i-2]

边界条件：

  • 字符 ‘0’ 不能单独解码
  • 组合数字必须在 10-26 范围内
  • 以 ‘0’ 开头的字符串无法解码

我们可以用空间优化的方式，只使用两个变量来存储前两个状态。

代码实现

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        
        int n = s.length();
        int prev2 = 1; // dp[i-2]
        int prev1 = 1; // dp[i-1]
        
        for (int i = 1; i < n; i++) {
            int curr = 0;
            
            // 单独解码当前字符
            if (s[i] != '0') {
                curr += prev1;
            }
            
            // 与前一个字符组合解码
            int twoDigit = (s[i-1] - '0') * 10 + (s[i] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                curr += prev2;
            }
            
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0
        
        n = len(s)
        prev2 = 1  # dp[i-2]
        prev1 = 1  # dp[i-1]
        
        for i in range(1, n):
            curr = 0
            
            # 单独解码当前字符
            if s[i] != '0':
                curr += prev1
            
            # 与前一个字符组合解码
            two_digit = int(s[i-1:i+1])
            if 10 <= two_digit <= 26:
                curr += prev2
            
            prev2 = prev1
            prev1 = curr
        
        return prev1

public class Solution {
    public int NumDecodings(string s) {
        if (string.IsNullOrEmpty(s) || s[0] == '0') return 0;
        
        int n = s.Length;
        int prev2 = 1; // dp[i-2]
        int prev1 = 1; // dp[i-1]
        
        for (int i = 1; i < n; i++) {
            int curr = 0;
            
            // 单独解码当前字符
            if (s[i] != '0') {
                curr += prev1;
            }
            
            // 与前一个字符组合解码
            int twoDigit = (s[i-1] - '0') * 10 + (s[i] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                curr += prev2;
            }
            
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
    if (!s || s[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串一次，其中 n 是字符串长度
空间复杂度O(1)只使用常数额外空间，空间优化版本

相关题目