1849. 将字符串拆分为递减的连续值

🎯 问题描述（来源于LeetCode）

描述：
给定一个字符串 s，判断是否能将其拆分成一个或多个连续递减 1 的整数序列（至少两个整数）。
每个子串表示一个整数，且不能有前导零（除非整数本身就是 0）。
拆分时必须使用所有字符，子串顺序不变。

说明：

数字序列应为 k, k-1, k-2, ... 的形式。
例如 "1234" 可以拆成 [1,2,3,4]，但这里要求递减，所以 "4321" 可以拆成 [4,3,2,1]。
注意：0 的特殊性，例如 "1001" 可以拆成 [10,0,1]？这里不连续，所以不行。

示例：

示例 1：

1
2
3

输入: s = "1234"
输出: false
解释: 无法拆分成递减1的连续整数序列（只有递增）。

示例 2：

1
2
3

输入: s = "050043"
输出: true
解释: 可以拆成 ["05","00","43"]？不对，数字应为 5,4,3？实际原题示例为 "4321" 是 true。此处请以原题为准。

示例 3：

1 2	输入: s = "9080701" 输出: false

💻 解题思路

思路：回溯法（DFS）尝试切分

算法步骤

获取字符串长度 n，初始化栈 stack 用于存储已确定的数字。
定义递归函数 dfs(i, cur)，其中 i 表示当前处理到的下标，cur 表示当前正在累积的子串（尚未切分）：
- 如果 i == n（已经遍历完所有字符）：
  - 如果 cur 非空（表示还有最后一段未切分），则将其转为数字 num。
    - 若栈为空（说明只有一段），返回 False。
    - 否则检查 num == stack[-1] - 1，若是则返回 True，否则 False。
  - 如果 cur 为空（说明已经切分到最后），则返回 len(stack) >= 2（至少两个数字）。
- 否则，分两种情况：
  - 不切分：将当前字符追加到 cur，递归 dfs(i+1, cur + s[i])，如果返回 True 则直接返回。
  - 切分：如果 cur 非空（即当前累积了一段子串），则将其转为整数 num：
    - 如果栈为空，则将 num 入栈，递归 dfs(i+1, s[i])，然后回溯出栈。
    - 如果栈非空，检查 num == stack[-1] - 1，若满足则入栈并递归，否则不进行切分。
    - 递归返回 True 则直接返回。
- 若所有分支均失败，返回 False。
从 dfs(0, "") 开始搜索。
返回最终结果。

代码实现

from typing import List

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)
        stack = []
        
        def dfs(i, cur):
            if i == n:
                if cur:
                    num = int(cur)
                    if not stack:
                        return False
                    if num == stack[-1] - 1:
                        return True
                    else:
                        return False
                else:
                    return len(stack) >= 2
            # 不切分
            if dfs(i+1, cur + s[i]):
                return True
            # 切分
            if cur:
                num = int(cur)
                if not stack:
                    stack.append(num)
                    if dfs(i+1, s[i]):
                        return True
                    stack.pop()
                else:
                    if num == stack[-1] - 1:
                        stack.append(num)
                        if dfs(i+1, s[i]):
                            return True
                        stack.pop()
            return False
        
        return dfs(0, "")