@laigary.com~/interview/coding/91-decode-ways.md$
$ cat ./coding/91-decode-ways.md
[Coding]·2023-01-28·15 min read

91. Decode Ways

91. 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。

所以骨架直接照抄爬樓梯：

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 一次擋掉這兩種：

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) - 11站在最後一位而且不是 '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' 會被當成一個合法的單字母解：

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'，最後才是「站在最後一位」。

解題方向

純遞迴

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 的完全無關。 確認了就加一行裝飾器：

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 面試技巧。

Bottom-Up

Top-down 是從 0 往後拆，bottom-up 反過來 —— 從字串尾巴往前填。dp[i] 的定義跟遞迴版一字不差：s[i:] 有幾種解碼方式。

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」。這是邊界哨兵的典型用法：讓 dp[i + 1] 和 dp[i + 2] 在 i 接近尾端時不必特判。

因為 dp[i] 只依賴 dp[i + 1] 和 dp[i + 2]，所以迴圈必須由後往前跑。

滾動變數

上一版每個格子只用到後面兩格，那整個陣列就是浪費 —— 兩個變數就夠了：

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爬 1 階或 2 階是幾種走法
746. Min Cost Climbing Stairs同上，但每階有成本是最小成本
91吃 1 位或 2 位數字否，受 10~26 和 '0' 限制幾種切法
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(2n) 上界，實際的分支數就是費氏數列，成長速度 O(φ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)

四種寫法都要掃過每個字元一次，差別只在存了多少東西。面試講到滾動變數這一版就很完整了。

--tags#Dynamic Programming
← cd ../codingcd ~