題目描述:
給定一個只包含數字的字串 s,判斷是否可以將其分割成兩個或更多的非空子串,使得相鄰子串的數值差恰好為 1,且按遞減順序排列。前導零是允許的(例如 "0" 和 "00" 都代表數值 0)。
解題思路: 使用回溯法(backtracking)。
first)。first - 1、first - 2、...,逐段切割。unsigned long long 或逐位比較避免溢位。由於字串最長 20 位,第一段的數值可能很大,需要注意數值溢位問題。
時間複雜度: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。可以完全避免溢位問題,但字串比較的實現較為繁瑣。