一條編碼訊息只包含數字，其中 ‘A’ = 1, ‘B’ = 2, …, ‘Z’ = 26。給定一個只含數字的字串
s，求有多少種不同的解碼方式。
Example:
Input: s = “226” Output: 3
Intuition
TIP
每個位置可以取一位或兩位數字解碼，類似爬樓梯但有條件限制。
- 如果當前字元不是 ‘0’，可以單獨解碼（取一位）
- 如果和前一個字元組成的兩位數在 10~26 之間，可以合併解碼（取兩位）
- ‘0’ 不能單獨解碼，是主要的邊界條件
Approaches
1. Bottom-Up DP Array — O(n) / O(n)
- Idea:
dp[i]表示前i個字元的解碼方式數，根據一位/兩位判斷轉移 - Time:
O(n) - Space:
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 — O(n) / O(1)
- Idea: 只保留前兩個狀態，用兩個變數替代 DP 陣列
- Time:
O(n) - Space:
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: 條件分支的費氏數列變體 — 不是每步都能跳，需要檢查有效性
- Key trick: 處理 ‘0’ 是重點：‘0’ 不能單獨解碼，只能和前一位組成 10 或 20