給定一個只包含數字的字串
s，判斷是否能將其分割成兩個以上的子字串，使得分割後的數值嚴格遞減且相鄰差為 1。前導零是允許的（如 “050” 可以表示 50）。
Example:
Input: s = “0090089” Output: true（分割為 “0090”, “089” 即 90, 89）
Intuition
TIP
核心思路：回溯嘗試第一段數值後，後續每段必須恰好比前一段小 1。
- 第一段可以是任意長度（1 到 n-1），決定了起始值
- 確定起始值後，後續每段的目標值是固定的（前一段 - 1）
- 用回溯法嘗試不同的第一段切法
- 注意：數字可能很大，需要用 Long 或 BigDecimal
Approaches
1. Enumerate First Segment + Recursive Verify — O(n²) / O(n)
- Idea: 外層枚舉第一段長度定下首值，
check從該點起要求每段都恰為prev-1（可變長度、允許前導零） - Time:
O(n²) - Space:
O(n)- 遞迴深度
class Solution {
fun splitString(s: String): Boolean {
for (firstLen in 1 until s.length) { // 第一段不可用完整串
val first = s.substring(0, firstLen).toLongOrNull() ?: break
if (check(s, firstLen, first)) return true
}
return false
}
// 從 start 起，後續每段都必須等於 prev-1
private fun check(s: String, start: Int, prev: Long): Boolean {
if (start == s.length) return true
var num = 0L
for (end in start until s.length) {
num = num * 10 + (s[end] - '0')
if (num == prev - 1 && check(s, end + 1, prev - 1)) return true
if (num >= prev) break // 已超過目標，再加位數只會更大
}
return false
}
}⭐ 2. Backtracking — O(n^2) / O(n)
- Idea: 嘗試所有可能的第一段切法，確定起始值後遞迴驗證後續段是否能依序遞減 1
- Time:
O(n^2)- n 為字串長度 - Space:
O(n)- 遞迴深度
class Solution {
fun splitString(s: String): Boolean {
fun backtrack(start: Int, prev: Long, count: Int): Boolean {
if (start == s.length) {
return count >= 2
}
var num = 0L
for (end in start until s.length) {
num = num * 10 + (s[end] - '0')
// 防止溢位
if (num < 0) break
if (count == 0) {
// 第一段，嘗試各種切法（不能取完整個字串）
if (end < s.length - 1 && backtrack(end + 1, num, 1)) {
return true
}
} else {
if (num == prev - 1) {
if (backtrack(end + 1, num, count + 1)) {
return true
}
}
// 若 num 已經 >= prev，繼續加位數只會更大，可以剪枝
if (num >= prev) break
}
}
return false
}
return backtrack(0, 0, 0)
}
}🔑 Takeaways
- Pattern: 字串分割 + 數值關係驗證 → 回溯嘗試切割點
- Key trick: 第一段決定起始值後搜索空間大幅縮小；注意 Long 溢位問題；當目前數值已超過目標時可提前剪枝