一魚多吃 用DP計算解碼的方法數 Decode Ways_Leetcode #91

Safar Safarov on Unsplash

題目敘述

題目會告訴我們一組英文和數字之間的轉換編碼規則，還有一個輸入字串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 <= 100
• s contains 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特訓班目錄 和 學習路徑