1849. Splitting a String Into Descending Consecutive Values

Medium
Description

給定一個只包含數字的字串 s，判斷是否能將其分割成兩個以上的子字串，使得分割後的數值嚴格遞減且相鄰差為 1。前導零是允許的（如 “050” 可以表示 50）。

Example:

Input: s = “0090089” Output: true（分割為 “0090”, “089” 即 90, 89）

Intuition#

核心思路：回溯嘗試第一段數值後，後續每段必須恰好比前一段小 1。

  • 第一段可以是任意長度（1 到 n-1），決定了起始值
  • 確定起始值後，後續每段的目標值是固定的（前一段 - 1）
  • 用回溯法嘗試不同的第一段切法
  • 注意：數字可能很大，需要用 Long 或 BigDecimal

Approaches#

⭐1: 回溯法#

  • 概念: 嘗試所有可能的第一段切法，確定起始值後遞迴驗證後續段是否能依序遞減 1
  • 時間複雜度: O(n^2) - n 為字串長度
  • 空間複雜度: 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: 字串分割 + 數值關係驗證 → 回溯嘗試切割點
  • 關鍵技巧: 第一段決定起始值後搜索空間大幅縮小；注意 Long 溢位問題；當目前數值已超過目標時可提前剪枝