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

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

难度中等5

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

深搜切分位置+BigInteger（暴力解法）

• 如果在满足切分条件的情况下能够切分到末尾，那么就可以满足返回true
• 如果在满足去切分条件的情况下不能切分到末尾，不可以满足返回false

import java.math.BigInteger;
class Solution {
    public boolean splitString(String s) {
        flag = false;
        dfs(s, new BigInteger(String.valueOf(0)), 0);
        return flag;
    }

    boolean flag = false;

    public void dfs(String s, BigInteger last, int index) {
        int n = s.length();
        if (index >= n) return;

        for (int i = index + 1; i <= n; i++) {
            BigInteger val = new BigInteger(s.substring(index, i));
            if (index == 0) {
                dfs(s, val, i);
            } else {
                if (val.compareTo(last) < 0 &&
                    last.subtract(val).equals(new BigInteger("1"))) {
                    dfs(s, val, i);
                    if (i == n) flag = true;
                }
            }
        }
    }
}

赏

谢谢你请我吃糖果

微信