Leetcode 639 解码方法

题目描述

一条包含字母 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" 不同。

除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回解码该字符串的方法数目。

由于答案数目可能非常大，返回 109 + 7 的模。

方法：动态规划

dp[i]：对于s的前i个元素的解码数量，dp[0]=1
非零性：*只能代表非0的数字
循环方式：外循环i表示下标位置，内循环j表示试图匹配的字母顺序，从1到26
更新方法：研究是否可以匹配一位数，研究是否可以匹配两位数

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution:
    def numDecodings(self, s: str) -> int:
        # 获取字符串的长度
        n = len(s)
        # 动态规划数组，dp[i]表示前i个字符的解码方法数
        dp = [0] * (n+1)
        # 空字符串有一种解码方式，即空字符串本身
        dp[0] = 1 
        # 取模值，防止结果溢出
        MOD = 10**9+7

        # 遍历字符串的每个字符
        for i in range(1, n+1):
            # 遍历可能的解码数字（1到26）
            for j in range(1, 27):
                # 当前字符
                cur = s[i-1]
                # 如果j是一个1位数（1到9）
                if j < 10:
                    # 如果当前字符等于j的字符串表示，或者当前字符是'*'
                    if cur == str(j) or cur == '*':
                        # 解码方法数增加 dp[i-1] 的数值，因为当前字符可以被单独解码
                        dp[i] += dp[i-1]
                # 如果j是一个2位数（10到26），并且i > 1 位置放得下
                elif i > 1:
                    # 前一个字符
                    pre = s[i-2]
                    # 检查当前字符是否等于j的个位，或者当前字符是'*'且j的个位不为0
                    if cur == str(j % 10) or (cur == '*' and j % 10):
                        # 检查前一个字符是否等于j的十位
                        # 或者前一个字符是'*'且j的十位不为0
                        if pre == str(j // 10) or (pre == '*' and j // 10):
                            # 解码方法数增加 dp[i-2] 的数值
                            # 因为当前字符和前一字符可以组成一个两位数解码
                            dp[i] += dp[i-2]
                # 对结果取模，防止溢出
                dp[i] %= MOD

        # 返回前n个字符的解码方法数
        return dp[n]