解码方法

难度: Medium

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

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

示例 2：

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

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

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

Submission

运行时间: 15 ms

内存: 16.0 MB

class Solution:
    def numDecodings(self, s: str) -> int:
        dp=[-1]*len(s)
        ans=0
        def f(i):
                nonlocal ans
            # if i not in d:
                if i==len(s):
                    return 1
                if dp[i]==-1:
                    if s[i]!='0':
                        ans=f(i+1)
                        if i+1 <len(s) and(s[i]=='1' or ( s[i]=="2" and s[i+1]<='6')):
                         ans+=f(i+2)
                    else:
                        ans=0
                    dp[i]=ans
                return dp[i]
        return f(0)

Explain

这个题解使用动态规划的思想来解决问题。它定义了一个函数f(i)，表示从字符串s的第i个字符开始到末尾的子串有多少种解码方式。然后使用递归的方式，从字符串的最后一个字符开始，逐步计算每个位置的解码方式数量，并将结果存储在dp数组中，避免重复计算。最终返回f(0)，即整个字符串s的解码方式总数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def numDecodings(self, s: str) -> int:
        dp=[-1]*len(s)  # DP数组，用于存储中间结果
        ans=0  # 解码方式总数
        
        def f(i):
            nonlocal ans
            if i==len(s):  # 递归的终止条件，到达字符串末尾
                return 1
            if dp[i]==-1:  # 如果当前位置的结果还没有计算过
                if s[i]!='0':  # 如果当前字符不为'0'
                    ans=f(i+1)  # 递归计算考虑当前字符单独解码的情况
                    if i+1 <len(s) and(s[i]=='1' or ( s[i]=='2' and s[i+1]<='6')):  # 如果当前字符和下一个字符可以组成有效的解码
                        ans+=f(i+2)  # 递归计算考虑当前字符和下一个字符一起解码的情况
                else:
                    ans=0  # 如果当前字符为'0'，无法解码，返回0
                dp[i]=ans  # 将当前位置的解码方式数量存入DP数组
            return dp[i]  # 返回当前位置的解码方式数量
        
        return f(0)  # 调用函数f(0)，计算整个字符串的解码方式总数

Explore

在动态规划解法中，dp数组初始化为-1表示该位置的解码方式尚未被计算。选择-1作为初始化值是因为解码方式的数量是非负数，使用-1可以明确区分出哪些位置的解码方式已经被计算过（非-1值），哪些还没有被计算（-1值）。这样可以确保每个位置的解码方式只被计算一次，避免不必要的重复计算，提高算法效率。

是的，当s[i]为'0'时，按照题目的解码规则，'0'不能单独被解码（没有对应的字母），并且不可以作为两位数的开始（如'01'，'02'等也都不是有效的解码）。因此，如果某位置的字符为'0'，这个位置就不会对解码总数做出贡献。递归函数在遇到'0'时直接返回0，意味着任何以'0'开头的子串都不会有有效的解码方式。

动态规划的递归处理字符串s的最后一个字符是通过检查是否到达字符串的末尾来实现的。递归函数f(i)中，当i等于字符串长度len(s)时，表示已经处理完所有字符，此时递归到达终止条件，返回1，因为到达字符串末尾是一种有效的结束方式（即之前的所有解码都有效）。

根据题目的解码规则，只有当数字组合在'10'到'26'之间时，它们才可以被一起解码成一个字母。这是因为这些数字对应于英文字母表的'A'到'Z'。如果s[i]为'2'并且s[i+1]为'7'或更大时（如'27'、'28'等），这些组合超出了'26'的范围，因此不能将它们一起解码为一个字母。所以在这种情况下，这两个字符不能被视为一个有效的两位数解码，递归函数不考虑将它们一起解码。