MediumRating 1747
1849. Splitting a String Into Descending Consecutive Values
stringbacktrackingenumeration
解題說明
Splitting a String Into Descending Consecutive Values
題目描述：
給定一個只包含數字的字串 s，判斷是否可以將其分割成兩個或更多的非空子串，使得相鄰子串的數值差恰好為 1，且按遞減順序排列。前導零是允許的（例如 "0" 和 "00" 都代表數值 0）。
解題思路： 使用回溯法（backtracking）。
- 枚舉第一段的長度（決定了起始數值
first）。 - 從剩餘字串中，嘗試匹配
first - 1、first - 2、...，逐段切割。 - 若能成功切割到字串末尾，且至少分成 2 段，回傳 true。
- 注意使用
unsigned long long或逐位比較避免溢位。
由於字串最長 20 位，第一段的數值可能很大，需要注意數值溢位問題。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 外層枚舉第一段長度 O(n)，內層 dfs 每次至多嘗試 O(n) 種分割長度。由於字串最長 20，實際複雜度很低。
空間複雜度：O(n) — 遞迴深度和子串建立各需 O(n)。
虛擬碼
1. For each possible length len of the first segment (1 to n-1):
a. Parse first segment as number 'first'
b. If first is too large (overflow), skip
c. Call dfs(s, len, first - 1) to try matching remaining segments
2. dfs(s, start, expected):
a. If start == s.length, return true (successfully split)
b. Convert expected to string to know minimum segment length
c. Try segments of increasing length starting at 'start':
- Parse segment value
- If value == expected: recurse with dfs(s, start+segLen, expected-1)
- If value > expected: break (longer won't help)
d. Return false
3. Return false if no split works其他解法
純枚舉 O(n^n) 最壞情況：不做剪枝的暴力枚舉所有可能的分割方式，再逐一驗證是否遞減連續。由於 n <= 20 且有很多約束，暴力也能通過但效率低。
雙指標比較（避免大數）：不轉換為整數，直接用字串比較來判斷 segment == expected。可以完全避免溢位問題，但字串比較的實現較為繁瑣。
延伸思考
- 如果允許遞增連續（而非遞減），演算法需要如何修改？
- 如果要求找出所有合法的分割方式（而非僅判斷存在性），如何修改回溯？
- 如果字串長度可達 10⁵，暴力回溯不再可行，是否有多項式時間的解法？