# 0091. 解码方法 ## 题目地址(91. 解码方法) <https://leetcode-cn.com/problems/decode-ways/> ## 题目描述 ``` <pre class="calibre18">``` 一条包含字母 A-Z 的消息通过以下方式进行了编码： 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。 题目数据保证答案肯定是一个 32 位的整数。 示例 1： 输入："12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。 示例 2： 输入："226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。 示例 3： 输入：s = "0" 输出：0 示例 4： 输入：s = "1" 输出：1 示例 5： 输入：s = "2" 输出：1 提示： 1 <= s.length <= 100 s 只包含数字，并且可以包含前导零。 ``` ``` ## 前置知识 - 爬楼梯问题 - [动态规划](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路 这道题目和爬楼梯问题有异曲同工之妙。 这也是一道典型的动态规划题目。我们来思考： - 对于一个数字来说\[1,9\]这九个数字能够被识别为一种编码方式 - 对于两个数字来说\[10, 26\]这几个数字能被识别为一种编码方式 我们考虑用 dp\[i\]来切分子问题， 那么 dp\[i\]表示的意思是当前字符串的以索引 i 结尾的子问题。 这样的话，我们最后只需要取 dp\[s.length\] 就可以解决问题了。 关于递归公式，让我们`先局部后整体`。对于局部，我们遍历到一个元素的时候， 我们有两种方式来组成编码方式，第一种是这个元素本身（需要自身是\[1,9\]）, 第二种是它和前一个元素组成\[10, 26\]。 用伪代码来表示的话就是： `dp[i] = 以自身去编码（一位） + 以前面的元素和自身去编码（两位）` .这显然是完备的， 这样我们通过层层推导就可以得到结果。 ## 关键点解析 - 爬楼梯问题（我把这种题目统称为爬楼梯问题） ## 代码 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {string} s * @return {number} */</span> <span class="hljs-keyword">var</span> numDecodings = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">if</span> (s == <span class="hljs-params">null</span> || s.length == <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; } <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(s.length + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">1</span>; dp[<span class="hljs-params">1</span>] = s[<span class="hljs-params">0</span>] !== <span class="hljs-string">"0"</span> ? <span class="hljs-params">1</span> : <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">2</span>; i < s.length + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">const</span> one = +s.slice(i - <span class="hljs-params">1</span>, i); <span class="hljs-keyword">const</span> two = +s.slice(i - <span class="hljs-params">2</span>, i); <span class="hljs-keyword">if</span> (two >= <span class="hljs-params">10</span> && two <= <span class="hljs-params">26</span>) { dp[i] = dp[i - <span class="hljs-params">2</span>]; } <span class="hljs-keyword">if</span> (one >= <span class="hljs-params">1</span> && one <= <span class="hljs-params">9</span>) { dp[i] += dp[i - <span class="hljs-params">1</span>]; } } <span class="hljs-keyword">return</span> dp[dp.length - <span class="hljs-params">1</span>]; }; ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) ## 扩展 如果编码的范围不再是 1-26，而是三位的话怎么办？ 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。