# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。