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

难度: Medium

给你一个仅由数字组成的字符串 s 。

请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的数值按降序排列，且每两个 相邻子字符串 的数值之差等于 1 。

例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为 [90,89] 。这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。然而，所有这些拆分方法都不可行，因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。

如果可以按要求拆分 s ，返回 true ；否则，返回 false 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "1234"
输出：false
解释：不存在拆分 s 的可行方法。

示例 2：

输入：s = "050043"
输出：true
解释：s 可以拆分为 ["05", "004", "3"] ，对应数值为 [5,4,3] 。
满足按降序排列，且相邻值相差 1 。

示例 3：

输入：s = "9080701"
输出：false
解释：不存在拆分 s 的可行方法。

示例 4：

输入：s = "10009998"
输出：true
解释：s 可以拆分为 ["100", "099", "98"] ，对应数值为 [100,99,98] 。
满足按降序排列，且相邻值相差 1 。

提示：

1 <= s.length <= 20
s 仅由数字组成

Submission

运行时间: 26 ms

内存: 15.9 MB

class Solution:
    def splitString(self, s: str) -> bool:

        def dfs(index, prev):
            if index >= len(s):
                return True

            for j in range(index, len(s)):
                val = int(s[index:j+1])
                if val + 1 == prev and dfs(j+1, val):
                    return True

            return False


        for i in range(len(s) - 1):
            val = int(s[:i+1])
            if dfs(i+1, val):
                return True

        return False

Explain

此题解采用了递归和回溯的方法来解决问题。首先，定义一个辅助的递归函数 `dfs(index, prev)`，其中 `index` 代表当前考虑的起始位置，而 `prev` 是上一个数字。此函数试图从 `index` 开始，寻找一个数值，使得其恰好比 `prev` 小1。如果找到这样的数值，函数将递归调用自身，将探索索引向前移动。如果从某个位置开始，能够持续找到递减且差值为1的序列直到字符串末尾，那么返回 `true`。外层循环尝试不同的初始切割点，从而探索所有可能的拆分方式。如果任何一种拆分方式满足条件，整个函数返回 `true`，否则在所有尝试后返回 `false`。

时间复杂度: O(2^n)

空间复杂度: O(n)

class Solution:
    def splitString(self, s: str) -> bool:

        def dfs(index, prev):
            # 如果处理完整个字符串，返回真
            if index >= len(s):
                return True

            # 尝试所有可能的下一个数
            for j in range(index, len(s)):
                val = int(s[index:j+1])
                # 当找到一个合适的下一个数时，递归地继续处理
                if val + 1 == prev and dfs(j+1, val):
                    return True

            # 如果没有成功的递归，返回假
            return False

        # 尝试每个可能的初始数
        for i in range(len(s) - 1):
            val = int(s[:i+1])
            if dfs(i+1, val):
                return True

        # 如果所有尝试都失败了，返回假
        return False

Explore

题解中并未特别说明如何处理前导零的问题。通常，在处理数字字符串转换为整数的过程中，需要考虑前导零的情况，因为在 Python 中，将字符串 '01' 转换为整数会得到 1，这会自动忽略前导零。然而，为了避免逻辑上的错误，特别是在数值需要精确匹配前一个数减一的情况下，应当添加判断条件来确保不处理前导零的数值字符串，除非这个数字本身就是 '0'。例如，可以在递归前检查字符串是否以 '0' 开头且长度大于 1，如果是，则不将其作为有效的数值解析。

在题解中，选择从当前索引 index 到 j+1 作为一个数的界限，是为了确保能够遍历所有可能的数值长度。这种方法不会漏掉任何有效分割，因为它从单个字符的数值开始，逐渐增加到包括从 index 到整个字符串剩余部分的最长可能数值。这样可以确保每一个可能的数值都被考虑到。

题解中的方法在找到一个合适的下一个数（即数值正好比前一个数小1）时会立即进行递归。这种方法确实考虑了所有可能的分割方式，因为对每一个可能的数值都尝试了递归调用。如果递归调用返回 true，表示从当前数开始到字符串末尾可以形成有效的递减序列；如果返回 false，则继续寻找下一个可能的数。这确保了不只是专注于第一个匹配的数，而是尝试所有可能的分割方式直到找到一个有效的解决方案。

外层循环在尝试初始切割点时不包括字符串的最后一个字符，是因为至少需要两个数来形成一个递减的连续值序列。如果包括了最后一个字符作为初始切割点，那么剩余的部分将是空字符串，无法形成第二个数。因此，循环的终止条件设置为 len(s) - 1，确保至少留有一个字符用于形成第二个数。这样的设置是为了确保所有的切割点都能至少尝试形成一个有效的递减序列。