題目資訊

• 題目編號: 91
• 題目連結: Decode Ways
• 主題: String, Dynamic Programming

題目敘述

你截獲了一則被編碼成數字串的秘密訊息。該訊息透過以下映射進行解碼：

"1" -> 'A'  
"2" -> 'B'  
...  
"25" -> 'Y'  
"26" -> 'Z'

然而，在解碼訊息的過程中，你發現有很多不同的方法可以進行解碼，因為某些代碼包含在其他代碼中（如 "2" 和 "5" vs "25"）。

例如，"11106" 可以解碼為：

• "AAJF"，分組為 (1, 1, 10, 6)
• "KJF"，分組為 (11, 10, 6)
• 分組 (1, 11, 06) 無效，因為 "06" 不是有效的代碼（只有 "6" 是有效的）。

注意：可能存在無法解碼的字串。

給定一個只包含數字的字串 s，返回解碼它的方法數。如果整個字串無法以任何有效方式解碼，返回 0。

測試用例的生成確保答案符合32位整數。

範例 1：

輸入： s = "12"

輸出： 2

解釋：

"12" 可以解碼為 "AB" (1 2) 或 "L" (12)。

範例 2：

輸入： s = "226"

輸出： 3

解釋：

"226" 可以解碼為 "BZ" (2 26)、"VF" (22 6)、或 "BBF" (2 2 6)。

範例 3：

輸入： s = "06"

輸出： 0

解釋：

"06" 無法映射為 "F"，因為有首位零（"6" 與 "06" 不同）。在此情況下，字串不是有效編碼，故返回 0。

約束條件：

• $1 \leq s.\text{length} \leq 100$
• $s$ 僅包含數字並且可能包含首位零。

直覺

解碼字串成字母的問題，可以利用帶有記憶化功能的遞歸方法（亦即動態規劃）優雅地解決。關鍵的直覺在於識別數字字串中的每個子字串，可以被解釋為單個字母，或者在特定條件下，作為一對字母進行解碼，這提供了多種路徑來解碼整個字串。此問題類似於爬樓梯的問題，有多種方式可以到達頂端，而每一步可以看作是解碼一位或兩位數字。理解這個重疊子問題的性質，自然引導我們使用動態規劃作為解法。

解法

我們使用深度優先搜尋（DFS）策略，搭配動態規劃（DP）陣列來計算字串可以被解碼的數量。DP陣列用作緩存以儲存中間結果，以防止重複計算，從而優化遞歸方法。以下是該方法的詳細步驟分解：

1. 初始化：首先，我們初始化一個與輸入字串 $s$ 長度相同的 DP 陣列，並將每個位置設置為 -1。這個陣列將用來儲存從每個索引開始的子字串的解碼方式數量。值 -1 表示該索引的結果尚未計算。

2. 遞歸函數 dfs(s, i)：此函數旨在計算從索引 $i$ 開始的子字串的解碼方式數量。

   • 基礎案例：
     • 如果索引 $i$ 超過字串的長度，返回 0，因為這是無效的。
     • 如果 $i$ 在字串的末尾，返回 1，表示找到一條有效的解碼路徑。
   • 記憶化檢查：在繼續之前，檢查當前索引 $i$ 的結果是否已經計算並儲存在 DP 陣列中。如果是，返回已儲存的結果以避免重新計算。
   • 單位或雙位數解碼：
     • 如果當前索引 $i$ 的字符是'0’，則返回 0，因為'0’不能單獨作為一個有效編碼。
     • 檢查是否可以解碼一字符（若不是'0’則總是可以）或兩字符（若位於有效範圍 “10” 到 “26” 之內則可能）。如果可以進行對的解析（如 “10” 到 “26”），則從單步及雙步後的位置開始計算。
     • 使用遞歸的結果來填充當前 DP 位置。

3. 主函數 numDecodings(s)：此函數初始化並管理 DP 陣列，並從字串的開始位置呼叫 DFS 函數。

   • 清除 DP 陣列並調整大小以匹配輸入字串。
   • 從索引 0 開始 DFS，使用遞歸策略計算整個字串的解碼計數。

此方法有效地將解碼問題分解為可管理的子問題，運用遞歸和記憶化來探索每個可能的解碼路徑並有效地計算出所有有效排列的總數。

程式碼

C++

class Solution {
public:
    // 動態規劃陣列，用來儲存中間結果
    vector<int> dp;

    // 深度優先搜索輔助函數，用來計算解碼方式
    int dfs(string& s, int i) {
        // 如果索引超過字串大小，返回0，因為這是不合規的
        if (i > s.size()) return 0;
        
        // 如果索引在字串的末尾，表示找到了一種有效的方式
        if (i == s.size()) return 1;

        // 如果結果已經計算過，返回它來避免重複計算
        if (dp[i] != -1) return dp[i];

        // 如果當前字符是'0'，它不能被解碼成任何字母
        if (s[i] == '0') return dp[i] = 0;

        // 檢查是否可以解碼一個或兩個字符
        if (s[i] == '1' || (i < s.size() - 1 && s[i] == '2' && s[i + 1] >= '0' && s[i + 1] <= '6')) {
            return dp[i] = dfs(s, i + 1) + dfs(s, i + 2);
        }
        else {
            return dp[i] = dfs(s, i + 1);
        }
    }

    // 主函數，返回解碼方式的數量
    int numDecodings(string s) {
        // 清除dp陣列並調整其大小以符合輸入字串大小
        dp.clear();
        dp.resize(s.size(), -1);

        // 從字串開始進行深度優先搜索
        return dfs(s, 0);
    }
};

Python

class Solution:
    # 動態規劃陣列用於儲存中間結果
    dp = []

    # 深度優先搜尋輔助函數來計算解碼的方法數
    def dfs(self, s, i):
        # 如果索引超出字串的大小，回傳0表示無效
        if i > len(s):
            return 0
        
        # 如果索引在字串的末尾，表示找到一種有效的方法
        if i == len(s):
            return 1

        # 如果結果已經計算過，返回該結果以避免重複計算
        if self.dp[i] != -1:
            return self.dp[i]

        # 如果當前字元是'0'，則無法解碼成任何字母
        if s[i] == '0':
            return 0

        # 檢查是否能解碼一個或兩個字元
        if s[i] == '1' or (i < len(s) - 1 and s[i] == '2' and '0' <= s[i + 1] <= '6'):
            self.dp[i] = self.dfs(s, i + 1) + self.dfs(s, i + 2)
        else:
            self.dp[i] = self.dfs(s, i + 1)

        return self.dp[i]

    # 主函數返回解碼的方法數
    def numDecodings(self, s):
        # 清除dp陣列並調整其大小以符合輸入字串的大小
        self.dp = [-1] * len(s)

        # 從字串的開頭開始進行深度優先搜尋
        return self.dfs(s, 0)

複雜度分析

• 時間複雜度: 解法的時間複雜度為 $O(n)$，其中 $n$ 是字串 $s$ 的長度。這是因為每個狀態（由字串中的索引表示）最多只計算一次，並儲存在 dp 陣列中。遞迴包括兩種主要情況（取一個字符或取兩個字符），但由於結果被緩存，每個索引的計算均在常數時間內完成。

• 空間複雜度: 解法的空間複雜度為 $O(n)$，其中 $n$ 是字串 $s$ 的長度。這是由於使用了 dp 陣列進行備忘錄法，該陣列為字串的每個索引儲存中間結果。此外，遞迴棧空間在最壞情況下也可以達到 $O(n)$。