--- title: "91. Decode Ways" url: "https://laigary.com/interview/coding/91-decode-ways" type: "note" section: "coding" date: "2023-01-28" updated: "2026-07-31" tags: ["Dynamic Programming"] --- # 91. Decode Ways [91\. Decode Ways](https://leetcode.com/problems/decode-ways/) 給一串只由數字組成的字串，`'A'` 到 `'Z'` 分別編碼成 `"1"` 到 `"26"`，問這串數字有幾種解碼方式。 例如 `"12"` 可以拆成 `1|2`（`AB`）或 `12`（`L`），兩種。`"226"` 可以拆成 `2|2|6`、`22|6`、`2|26`，三種。而 `"06"` 一種都沒有 —— `06` 不是合法編碼，`0` 也不對應任何字母。 ## 思路 ### 這是一題爬樓梯 每次往前走，只有兩種選擇：**吃掉一個數字**（當成一位數的字母），或是**吃掉兩個數字**（當成兩位數的字母）。一次一步或兩步，這就是 [70. Climbing Stairs](/interview/coding/70-climbing-stairs)。 所以骨架直接照抄爬樓梯： ```python class Solution: def numDecodings(self, s: str) -> int: def recursive(index: int) -> int: # TODO 終止條件 ans = recursive(index + 1) ans += recursive(index + 2) return ans return recursive(0) ``` 差別在於，爬樓梯的每一步都合法，這題**不是**。所以真正的工作全部集中在「什麼時候不能走」。 ### 兩個限制 限制一，**兩位數只有 10 到 26 能走**。`"27"` 不對應任何字母，`"06"` 也不行（編碼沒有前導零）。用 `10 <= ... <= 26` 一次擋掉這兩種： ```python ans = recursive(index + 1) if 10 <= int(s[index:index + 2]) <= 26: ans += recursive(index + 2) ``` `int("06")` 是 6，小於 10，自然被擋下來，不需要另外寫前導零的判斷。 限制二，**`'0'` 不能單獨解碼**。`'0'` 只能當某個兩位數的第二位（`10`、`20`），永遠不可能自己站著。 ### 三個終止條件 把限制二和邊界一起處理，會得到三個終止條件： | 條件 | 回傳 | 為什麼 | |---|---|---| | `index == len(s)` | 1 | 走到底了，前面那套切法成立 | | `s[index] == '0'` | 0 | `'0'` 開頭無解，這條路死了 | | `index == len(s) - 1` | 1 | 站在最後一位而且不是 `'0'`，就是一種解 | 第一個回傳 1 是這題最不直覺的地方，值得單獨說。`recursive(index)` 的定義是「`s[index:]` 有幾種解碼方式」。當 `index == len(s)`，`s[index:]` 是**空字串**，而空字串恰好有一種解碼方式：什麼都不切。 它不是特例，是定義的自然延伸 —— 而且是整棵遞迴樹裡**唯一產生 1 的地方**。所有的答案都是這些 1 沿路加回去累積出來的。如果這裡回傳 0，等於宣告「不管前面怎麼切都不算數」，整題的答案會直接變成 0。 ### 順序不能換 這三個條件**有嚴格的先後順序**，而且兩個相鄰的交換都會出事： **`index == len(s)` 必須在最前面。** 否則下一行的 `s[index]` 直接 `IndexError`。這個錯很吵，一跑就發現。 **`s[index] == '0'` 必須排在 `index == len(s) - 1` 前面。** 這個錯很安靜。因為**最後一位有可能就是 `'0'`** —— 如果先問「是不是站在最後一位」，`"10"` 的那個 `'0'` 會被當成一個合法的單字母解： ```text s = "10"，先問 index == len(s) - 1 recursive(0)：不是最後一位 → 往下走 recursive(1)：index == 1 == len(s)-1 → 回傳 1 ← 錯，s[1] 是 '0' 10 在範圍內 → recursive(2)：越界 → 回傳 1 合計 2 正解是 1（只有 "10" → J） ``` 所以順序是：**先擋越界，再擋 `'0'`，最後才是「站在最後一位」**。 ## 解題方向 ### 純遞迴 ```python class Solution: def numDecodings(self, s: str) -> int: def recursive(index: int) -> int: # 要先處理越界，不然下一個條件會報錯 if index == len(s): return 1 # 再來要看是不是零，因為有可能最後一個數字是零 if s[index] == '0': return 0 # 沒有越界，也不是零，才是真的到達了終點 if index == len(s) - 1: return 1 ans = recursive(index + 1) if 10 <= int(s[index:index + 2]) <= 26: ans += recursive(index + 2) return ans return recursive(0) ``` 這份是對的，但會超時。以 `"1111111"` 為例，`recursive(2)` 可以從 `0 → 1 → 2` 到達，也可以從 `0 → 2` 到達，兩條路各算一整棵子樹。重疊子問題的形狀跟費氏數列一模一樣。 ### Top-Down：加上 `@cache` 能記憶化的前提是：**`recursive(index)` 只跟 `index` 有關，跟你是怎麼走到這個 `index` 的完全無關。** 確認了就加一行裝飾器： ```python class Solution: def numDecodings(self, s: str) -> int: @cache def dp(i: int) -> int: if i == len(s): return 1 if s[i] == '0': return 0 ans = dp(i + 1) if 10 <= int(s[i:i+2]) <= 26: ans += dp(i + 2) return ans return dp(0) ``` 這裡順手把 `i == len(s) - 1` 拿掉了 —— 它其實是多餘的，理由寫在補充。少一個條件，順序踩雷的機會也少一個。 `@cache` 來自 `functools`，用法見 [Python 面試技巧](/interview/coding/python-tips-for-interview)。 ### Bottom-Up Top-down 是從 0 往後拆，bottom-up 反過來 —— 從字串尾巴往前填。`dp[i]` 的定義跟遞迴版一字不差：`s[i:]` 有幾種解碼方式。 ```python class Solution: def numDecodings(self, s: str) -> int: n = len(s) dp = [0] * (n + 1) dp[n] = 1 # 空字串有一種解碼方式 for i in range(n - 1, -1, -1): if s[i] == '0': continue # dp[i] 維持 0 dp[i] = dp[i + 1] if 10 <= int(s[i:i+2]) <= 26: dp[i] += dp[i + 2] return dp[0] ``` `dp` 開 `n + 1` 格，多出來的 `dp[n]` 就是遞迴版的「越界回傳 1」。這是[邊界哨兵](/interview/coding/python-tips-for-interview)的典型用法：讓 `dp[i + 1]` 和 `dp[i + 2]` 在 `i` 接近尾端時不必特判。 因為 `dp[i]` 只依賴 `dp[i + 1]` 和 `dp[i + 2]`，所以迴圈**必須由後往前**跑。 ### 滾動變數 上一版每個格子只用到後面兩格，那整個陣列就是浪費 —— 兩個變數就夠了： ```python class Solution: def numDecodings(self, s: str) -> int: after_next, next_ = 0, 1 # dp[i+2], dp[i+1] for i in range(len(s) - 1, -1, -1): if s[i] == '0': curr = 0 else: curr = next_ if 10 <= int(s[i:i+2]) <= 26: curr += after_next after_next, next_ = next_, curr return next_ ``` 初始值 `next_ = 1` 對應 `dp[n]`，`after_next = 0` 是 `dp[n + 1]` —— 它從來不會被真正用到，因為 `i == n - 1` 時 `s[i:i+2]` 只有一個字元，永遠進不了 `10 <= ... <= 26`。給它 0 只是為了讓迴圈第一輪有東西可以讀。 ## 補充 ### 那個 `index == len(s) - 1` 可以拿掉 它不是必要的終止條件，只是一個提早回傳的捷徑。當 `index == len(s) - 1` 而且不是 `'0'` 時，讓遞迴繼續跑下去會發生： - `recursive(index + 1)` → `index + 1 == len(s)` → 回傳 1 - `s[index:index+2]` 只切得到一個字元，`int()` 落在 1 到 9，**永遠不在 10 到 26 之間**，第二個分支不會走 合計就是 1，跟直接回傳一模一樣。拿掉之後只剩兩個條件，而它們的順序是被 `IndexError` 強制的 —— 寫錯會馬上炸，不會像上面那樣安靜地算出錯答案。 ### 這題和爬樓梯家族 | 題目 | 一步／兩步的意義 | 每一步都合法嗎 | 要什麼 | |---|---|---|---| | [70. Climbing Stairs](/interview/coding/70-climbing-stairs) | 爬 1 階或 2 階 | 是 | 幾種走法 | | [746. Min Cost Climbing Stairs](/interview/coding/746-min-cost-climbing-stairs) | 同上，但每階有成本 | 是 | 最小成本 | | 91 | 吃 1 位或 2 位數字 | **否**，受 10~26 和 `'0'` 限制 | 幾種切法 | | [198. House Robber](/interview/coding/198-house-robber) | 偷或不偷（不能連兩間） | 是 | 最大金額 | 四題的 $f(i)$ 全部都只由 $f(i+1)$ 和 $f(i+2)$ 決定，差別只在合起來的方式是加總還是取極值，以及**有沒有條件擋住某些轉移**。91 的全部難度都在那個「擋」字上，遞迴的骨架本身反而是最簡單的部分。 ### 為什麼不需要處理 `'0'` 之後的狀態 看起來 `'0'` 好像要「回頭告訴前一位『我被你吃掉了』」，但其實不用。因為兩位數的分支是 `dp(i + 2)` —— 當 `s[i:i+2]` 是 `"10"` 時，程式直接跳過那個 `'0'`，根本不會有人以它為起點呼叫 `dp`。 會以 `'0'` 為起點被呼叫，只發生在「前一位選擇了走一步」的時候，而那正是應該回傳 0 的情況。所以一個 `return 0` 就把全部的零處理乾淨了。 ## 複雜度 以下用 $n$ 表示字串長度。 - **純遞迴** — 時間 $O(2^n)$ 上界，實際的分支數就是費氏數列，成長速度 $O(\varphi^n)$；空間 $O(n)$ 是遞迴深度 - **Top-down（`@cache`）** — 時間 $O(n)$，狀態只有 $n + 1$ 個而且每個是 $O(1)$；空間 $O(n)$ 是快取加上遞迴堆疊 - **Bottom-up** — 時間 $O(n)$；空間 $O(n)$ 只有 `dp` 陣列，沒有遞迴堆疊 - **滾動變數** — 時間 $O(n)$；空間 $O(1)$ 四種寫法都要掃過每個字元一次，差別只在存了多少東西。面試講到滾動變數這一版就很完整了。