LeetCode第九十一题—解码方法—Python实现

概述title:LeetCodeNo.91categories:OJLeetCodetags:ProgramingLeetCodeOJLeetCode第九十一题—解码方法题目描述一条包含字母A-Z的消息通过以下映射进行了编码：‘A’->1‘B’->2…‘Z’->26要解码已编码的消息，所有数字必须基于上述映射的方法，反向映

---

Title: LeetCode No.91

categorIEs:

OJLeetCode

Tags:

ProgramingLeetCodeOJ

---

LeetCode第九十一题—解码方法题目描述

一条包含字母 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 = "0"输出：0解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。示例 4：输入：s = "06"输出：0解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。 提示：1 <= s.length <= 100s 只包含数字，并且可能包含前导零。

代码

class Solution(object):    def numDeCodings(self, s):        """        :type s: str        :rtype: int        核心思想：动态规划                s[i]只包含数字，其可能为0                第一步：定义dp数组                    dp[i]表示前i个数字解码的个数，结果直接返回dp[-1]                第二步：确定状态转移方程                    状态转移方程表示了大规模的问题如何由小规模问题转换而来                    即如何用dp[i-1]...dp[0]来得到dp[i]                    本题分析：对于两个字符来说，只存在被解码成0种、1种、2种的情况，所以需要分别讨论上述情况是如何得到的                    具体讨论如下:                        ① s[i]不在合法集合中即s[i]为0，这是来考察si[i-1]+s[i]=[i-1:i+1]的                            - 对于0s[i]这种情况，必然不在合法集合中，直接返回0                            - 但是对于s[i]0这种情况，是存在合法情况的，如10 20                        ② s[i]在合法集合中，考察si[i-1]+s[i]=[i-1:i+1]的                            - s[i-1:i+1]不在合法集合中，即大于26或者小于1的情况，无法解码                            - s[i-1:i+1]在合法集合中，即在1-26之间，但是需要注意这种情况是可以进行拆分解码的                            拆分之后会影响后面的解码情况的        """        if s[0] == '0':            return 0        length = len(s)        if length == 1:            return 1        # 生成数组        legal = set(str(i) for i in range(1,27))        dp = [0] * length # 初始化dp数组        dp[0] = 1 # 设置s[0]对应的解码为1        if s[1] not in legal:  # s[1]为0            dp[1] = 1 if s[: 2] in legal else 0        else:            dp[1] = 2 if s[: 2] in legal else 1        for i in range(2,length):            # 处理剩下的情况  13023            ## 合法情况            if s[i] in legal:                if s[i-1:i+1] in legal:                    dp[i] = dp[i-1] + dp[i-2]                else:                    dp[i] = dp[i-1]            else:                if s[i-1:i+1] in legal:                    dp[i] = dp[i-2]                else:                    return 0        return dp[-1]if __name__ == '__main__':    s = Solution()    print(s.numDeCodings("12"))

总结

以上是内存溢出为你收集整理的LeetCode第九十一题—解码方法—Python实现全部内容，希望文章能够帮你解决LeetCode第九十一题—解码方法—Python实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。