题目描述

给你一个仅由数字组成的字符串 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。

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

样例

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

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

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

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

限制

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

算法

(递归回溯) $O(2^n)$

1. 对于每个非末尾的位置，都有两种决策：放置分隔符或者不放置分隔符。
2. 放置分隔符的时候，需要保证当前子串的值比上一个子串的值小 1。

时间复杂度

• 共有 $n-1$ 个位置可以防止分隔符，判断的时间为常数，故总时间复杂度为 $O(2^n)$。

空间复杂度

• 需要 $O(n)$ 的空间存储递归的系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    bool solve(int i, LL last, LL cur, const string &s) {
        if (cur >= 1000000000000ll)
            return false;

        if (i == s.size()) {
            if (cur == last - 1)
                return true;
            return false;
        }

        const LL ncur = cur * 10 + s[i] - '0';

        if (solve(i + 1, last, ncur, s))
            return true;

        if (i < s.size() - 1 && (last == -1 || ncur == last - 1))
            if (solve(i + 1, ncur, 0, s))
                return true;

        return false;
    }

public:
    bool splitString(string s) {
        return solve(0, -1, 0, s);
    }
};