91. Decode Ways

Medium

Description

一條編碼訊息只包含數字，其中 ‘A’ = 1, ‘B’ = 2, …, ‘Z’ = 26。給定一個只含數字的字串 s，求有多少種不同的解碼方式。

Example:

Input: s = “226” Output: 3

Intuition#

每個位置可以取一位或兩位數字解碼，類似爬樓梯但有條件限制。

如果當前字元不是 ‘0’，可以單獨解碼（取一位）
如果和前一個字元組成的兩位數在 10~26 之間，可以合併解碼（取兩位）
‘0’ 不能單獨解碼，是主要的邊界條件

Approaches#

1: Bottom-Up DP Array#

概念: dp[i] 表示前 i 個字元的解碼方式數，根據一位/兩位判斷轉移
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun numDecodings(s: String): Int {
        if (s[0] == '0') return 0
        val n = s.length
        val dp = IntArray(n + 1)
        dp[0] = 1
        dp[1] = 1
        for (i in 2..n) {
            val one = s[i - 1] - '0'
            val two = (s[i - 2] - '0') * 10 + one
            if (one in 1..9) dp[i] += dp[i - 1]
            if (two in 10..26) dp[i] += dp[i - 2]
        }
        return dp[n]
    }
}

⭐2: Rolling Variables#

概念: 只保留前兩個狀態，用兩個變數替代 DP 陣列
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun numDecodings(s: String): Int {
        if (s[0] == '0') return 0
        var prev2 = 1  // dp[i-2]
        var prev1 = 1  // dp[i-1]
        for (i in 2..s.length) {
            var cur = 0
            val one = s[i - 1] - '0'
            val two = (s[i - 2] - '0') * 10 + one
            if (one in 1..9) cur += prev1
            if (two in 10..26) cur += prev2
            prev2 = prev1
            prev1 = cur
        }
        return prev1
    }
}

🔑 Takeaways#

Pattern: 條件分支的費氏數列變體 — 不是每步都能跳，需要檢查有效性
關鍵技巧: 處理 ‘0’ 是重點：‘0’ 不能單獨解碼，只能和前一位組成 10 或 20