LeetCode刷题——91. 解码方法
版权申诉
24 浏览量
2020-12-20
21:12:58
上传
评论
收藏 79KB PDF 举报
LeetCode刷题刷题——91. 解码方法解码方法
题目题目
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
思路思路
这个题有点像爬楼梯，但是比爬楼梯复杂很多。有很多限制条件，甚至题目没给出来，比如不能以0开头，不能连续出现两个0。 总之分解之后的数值只能在[1,26]之间。
先用递归的思想，自顶向下的思考问题。这里的“顶”是指字符串最后一个字符。
如果连续两个数字符合条件([1,26]，如果像09这种，就不是两个数字符合条件，因为拆分成两个的话，会出现0和9, 0不符合条件。简单的方式是看这两个字符形成的数字
是不是在[10,26]之间。其中10在这之前被考虑过。)，
则有两种解法，一种是分成两个数字，还有一种是整个解成一个数字。
考虑限制条件比较麻烦，以下有先后顺序：
不能以0开头
不能出现连续两个0
如果当前数字不是0，则可以先将两个数字拆开解(解法1)
如果连续两个数字符合条件，则将两个数字一起解(解法2)
其他大于26的情况，只能拆开解，已经在第3步考虑过了
代码代码
递归递归
class Solution(object):
def num(self,s, i):
# 不能以0开头
if int(s[0]) == 0:
return 0
if i <= 0: # = 1 and int(s[i] + s[i - 1]) == 0:
return 0
res = 0
# 当前数字不是0
if int(s[i]) != 0:
# 先拆分一步
res = self.num(s, i - 1)
digit = int(s[i - 1] + s[i])
# 如果连续的两位数符合条件,有两种解法
if 10 <= digit <= 26:
res += self.num(s, i - 2)
return res
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
return self.num(s, len(s) - 1)
资源评论
weixin_38588592
- 粉丝: 3
- 资源: 922
最新资源
- IMG_5905.PNG
- Cyclone Version 9.51
- 高性能量化回测工具 hikyuu 2.0.3 python 3.12 windows 安装包
- 省级城乡居民基本养老保险情况数据集（2010-2022年）.xlsx
- 舞队填写版.cpp
- 基于BP神经网络的多输入单输出回归预测.zip
- 高性能量化回测工具 hikyuu 2.0.3 python 3.9 windows 安装包
- 省级城镇职工基本养老保险情况2000-2022年.xlsx
- 高性能量化回测工具 hikyuu 2.0.3 python 3.10 windows 安装包
- 算法部署-使用OpenVINO+C#部署PaddleOCR字符识别算法-项目源码-优质项目实战.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
