题目描述

给定一个只包含数字和非负整数范围内的字母的字符串，每个 'A' 到 'Z' 的字母可以表示从 '1' 到 '26' 的一个数字。现在，我们有一种方法来解码这个字符串，规则如下：

• 字符串中的每个字符单独解码为一个数字（1-9 会被解码为 1-9，0 不可以单独解码）。
• 或者，字符串中的两个字符（必须是 '10' 到 '26'）可以被解码为一个数字。

问这个字符串有多少种不同的解码方法？

示例

输入: "12" 输出: 2 解释: 它可以被解码为 "AB"（1 2）或者 "L"（12）。

输入: "226" 输出: 3 解释: 它可以被解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

输入: "0" 输出: 0 解释: 没有字符可以被解码为 '0'。

PHP 代码示例

function numDecodings($s) {
    $n = strlen($s);
    if ($n == 0 || $s[0] == '0') {
        return 0;
    }
    
    $dp = array_fill(0, $n, 0);
    $dp[0] = 1;
    
    for ($i = 1; $i < $n; $i++) {
        // 单个字符解码
        if ($s[$i] != '0') {
            $dp[$i] += $dp[$i - 1];
        }
        
        // 两个字符解码
        $twoDigit = intval(substr($s, $i - 1, 2));
        if ($twoDigit >= 10 && $twoDigit <= 26) {
            if ($i > 1) {
                $dp[$i] += $dp[$i - 2];
            } else {
                $dp[$i] += 1; // 第一个字符和第二个字符组成的两位数
            }
        }
    }
    
    return $dp[$n - 1];
}

// 测试
echo numDecodings("12") . "\n"; // 输出 2
echo numDecodings("226") . "\n"; // 输出 3
echo numDecodings("0") . "\n"; // 输出 0

Python 代码示例

def num_decodings(s: str) -> int:
    n = len(s)
    if n == 0 or s[0] == '0':
        return 0
    
    dp = [0] * n
    dp[0] = 1
    
    for i in range(1, n):
        # 单个字符解码
        if s[i] != '0':
            dp[i] += dp[i - 1]
        
        # 两个字符解码
        two_digit = int(s[i-1:i+1])
        if 10 <= two_digit <= 26:
            if i > 1:
                dp[i] += dp[i - 2]
            else:
                dp[i] += 1
    
    return dp[-1]

# 测试
print(num_decodings("12"))  # 输出 2
print(num_decodings("226"))  # 输出 3
print(num_decodings("0"))  # 输出 0

JavaScript 代码示例

function numDecodings(s) {
    const n = s.length;
    if (n === 0 || s[0] === '0') {
        return 0;
    }
    
    const dp = new Array(n).fill(0);
    dp[0] = 1;
    
    for (let i = 1; i < n; i++) {
        // 单个字符解码
        if (s[i] !== '0') {
            dp[i] += dp[i - 1];
        }
        
        // 两个字符解码
        const twoDigit = parseInt(s.substring(i - 1, i + 1));
        if (twoDigit >= 10 && twoDigit <= 26) {
            if (i > 1) {
                dp[i] += dp[i - 2];
            } else {
                dp[i] += 1;
            }
        }
    }
    
    return dp[n - 1];
}

// 测试
console.log(numDecodings("12")); // 输出 2
console.log(numDecodings("226")); // 输出 3
console.log(numDecodings("0")); // 输出 0

码小课网站中有更多相关内容分享给大家学习，包括算法题解、数据结构、编程技巧等，欢迎访问学习。