從LeetCode學演算法 - 83 Dynamic Programming (10)

0091. Decode Ways (Medium)

Question

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1

1
2
3
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2

1
2
3
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

分析/解題

給定一個訊息，當中A到Z以1至26的方式依序對應，
用數字的編碼方式寫成一個字串。
給定這樣子一個僅含數字1~9組成的字串，
試決定所有可以解碼的方法數。

這題在LeetCode上面比較有問題的點在於，
沒有硬性規定開頭或結尾多出來的0 的部分。
所以這邊我們會再加上一個條件，
一旦開頭有0或中間有碰到多餘的0 的部分，
就當作可以接續下去(不當作錯誤)，
這樣看起來會比較符合測資測出來的結果。

首先會考慮到就當下而言，如果是空字串的話，
應該要直接先回傳0**(雖然沒有字串嚴格來說也是1種方法，
但給題目來說就要代表沒有辦法解碼)。
如果是考慮每個字串起始檢查的狀況，
則應該會將起始條件設定為1種可能。**

接下來我們考慮往下走的時候，怎麼樣可以構成可能的字組呢？
我們假定從index 0開始的各種子字串，
均已知有幾種方法了，那麼，當我們在index i的位置時，
要如何決定到這邊的方法數呢？其實不難思考。

由於我們的英文字母可能性是從126，
所以如果**index i對應的值是19之間** 的話，
代表它獨立可以成為一種可能性，
也就是走到前面i-1的狀況，再加上i這邊單獨代表的字母 。
這麼考慮的話走到i的組合數就和走到i-1的組合數是相同的 。
(以index i位置的值單獨成立的狀況來說)

那麼還有另一種可能，
就是index i-1和index i所組成的二位數也能代表字母，
這個數字應該是10~26 之間，所以這種狀況成立的條件下，
走到i的組合數和走到i-2的組合數相同 。

所以歸納上述兩點，我們必須要分別檢查，
然後決定是否要將i-1的方法數及i-2的方法數加進來。

感覺是不是有點像之前的House Robber?
所以這也是一個典型的Dynamic Programming題目。
依此，我們可以定一個array或list，取名叫dp ，
長度為s的長度加1。

我們將可能的兩位數分別叫做prev跟curr，
那麼每次要作的事情，就如同上面所述一樣：

初始化dp[0] = 1 ,
dp[1] = 1 (如果第一個字不是'0’) or 0 (如果第一個字是'0’)
迴圈讓i從2l，
每次將curr的值遞移到prev，prev則取得s[i-1] 的值。
當curr非0 的時候(即19)，我們可以將dp[i-1]加到dp[i] 中；
當prev和curr 可以組成10~26之間 的值時，可以將dp[i-2]加到dp[i] 中。
迴圈結束後，回傳dp[l] 即可。

依此，寫成程式碼如下。

Java

Java的部分，也可以順便檢查s是否為null，
但本題的測資似乎也沒有刁難這個部分(題目有說均為數字)。
檢查10~26 的部分，
可以拆成(prev==’1’) 或(prev == ‘2’且curr ≤ ’6’) 檢驗。對Java而言，
char可以直接用數字的方式(ASCII Code)的狀態來比大小，
所以我們不用再轉成Integer來浪費時間XD

Python

Python的部分，也可以直接比大小 ，其實作是呼叫ord()函數，
來取得比大小所需的ASCII Code數字，
但就沒辦法像Java的char那樣很多花樣了。

提醒大家，在寫的時候請務必留意範圍，
以本題為例，由於dp[0] 是被佔用做為初始值的，
所以我們在寫的時候i是對應由1為準起算的。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，N為字串長度)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**