0091. 解码方法
题目地址(91. 解码方法)
https://leetcode-cn.com/problems/decode-ways/
题目描述
前置知识
爬楼梯问题
公司
阿里
腾讯
百度
字节
思路
这道题目和爬楼梯问题有异曲同工之妙。
这也是一道典型的动态规划题目。我们来思考:
对于一个数字来说[1,9]这九个数字能够被识别为一种编码方式
对于两个数字来说[10, 26]这几个数字能被识别为一种编码方式
我们考虑用 dp[i]来切分子问题, 那么 dp[i]表示的意思是当前字符串的以索引 i 结尾的子问题。这样的话,我们最后只需要取 dp[s.length] 就可以解决问题了。
关于递归公式,让我们先局部后整体
。
对于局部,我们遍历到一个元素的时候,有两种方式来组成编码方式,第一种是这个元素本身(需要自身是[1,9]),第二种是它和前一个元素组成[10, 26]。
用伪代码来表示的话就是:dp[i] = 以自身去编码(一位) + 以前面的元素和自身去编码(两位)
,这显然是完备的,这样我们就通过层层推导得到结果。
关键点解析
爬楼梯问题(我把这种题目统称为爬楼梯问题)
代码
代码支持: JS, Python3,CPP
JS Code:
Python3 Code:
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(N)$
实际上,我们也可以使用滚动数组优化。
CPP code:
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
扩展
如果编码的范围不再是 1-26,而是三位的话怎么办?
最后更新于
这有帮助吗?