一魚多吃 用DP計算解碼的方法數 Decode Ways_Leetcode #91
題目敘述
題目會告訴我們一組英文和數字之間的轉換編碼規則，還有一個輸入字串s，問我總共有多少合法的解碼方式?
要特別留意，輸入字串可能包含有leading zero，導致無法解碼。
轉換規則如下:
A <-> 1
B <-> 2
C <-> 3
...
Z <-> 26
測試範例
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
約束條件
Constraints:
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
一樣，再次強調DP的解題框架，鞏固知識點。
Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。
Dynamic programming的解題框架可分為三大步驟
1. 定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
1. 定義狀態 [我在哪裡]
這一題題目很明確要求，就是計算解碼的方法數。
我們可以令DP[ i ] 代表字串s[0] ~ s[i]的解碼總方法數。
那麼，題目所求就變成 DP[ n-1 ], where n = len(s) = 字串s的長度
2. 定義狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]
編碼寬度為2，1~26，有兩種可能的解碼途徑
第一種可能情況:
最後一個數字落在1~9之間，可以解碼最後一個數字。
DP[ i ] += DP[ i-1 ], if 1 <= int( s[i] ) <= 9
第二種可能情況:
最後兩個數字落在10~26之間，可以一口氣解碼最後兩個數字
DP[ i ] += DP[ i-2 ], if i >= 1 and 10 <= int( s[i-1 : i+1] ) <= 26:
3. 釐清初始狀態(終止條件)
[第一步怎麼走，怎麼出發的]
要特別留意，輸入字串可能包含有leading zero，導致無法解碼。
所以當s[0] == "0"的時候，代表無法解碼，可以直接返回DP[0] = 0，不存在任何合法解碼方式。
另一方面，若s[0] != "0"，代表存在唯一一種解碼方式，就是int(s[0])本身的數字，這時候DP[0] = 1。
最後，空字串 ""也只有一種解碼方式，就是空字串本身，DP[-1] = 1
程式碼
class Solution:
def numDecodings(self, s):
# Empty string, only one way to decode
dp = {-1: 1}
if s[0] != "0":
dp[0] = 1
else:
# Leading zero, this string cannot be decoded.
dp[0] = 0
return 0
def decode( i ):
# look up DP table to avoid repeated computation
if i in dp:
return dp[i]
count = 0
# current digit is valid, try to decode prefix string without current digit
if 1 <= int(s[i]) <= 9:
count += decode(i-1)
# current last two digits are valid, try to decode prefix string without current last two digits
if i >= 1 and 10 <= int(s[i-1:i+1]) <= 26:
count += decode(i-2)
# update DP table
dp[i] = count
return count
# ====================================
return decode( len(s)-1 )
複雜度分析
時間複雜度:O(n)
其實仔細看，會發現每個index最多有兩條可行的分支，有點像是帶有條件的費式數列的變形DP[i] = DP[i-1] (如果最後一個數字可以解碼) + DP[i-2] (如果最後兩個數字可以解碼)
空間複雜度:O(n)
主要成本落在DP table: dp這個字典，還有decode()遞迴呼叫的最大深度，最深和字串長度len(s)一樣長。
Reference
[1] Python/JS/C++ O(n) by DP // Recursion [w/ Example] - Decode Ways - LeetCode
回到DP特訓班目錄 和 學習路徑
你可能也想看
