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
解释: 没有有效的拆分方式。

示例 2：

输入: s = "050043"
输出: true
解释: s 可以拆分为 ["05", "004", "3"]，数值为 [5,4,3]。
这些数值按降序排列，相邻数值的差为 1。

示例 3：

输入: s = "9080701"
输出: false
解释: 没有有效的拆分方式。

约束：

  • 1 <= s.length <= 20
  • s 只包含数字。

解题思路

这道题可以使用回溯算法来解决。核心思路是尝试所有可能的拆分方式，检查是否满足递减且相邻差为1的条件。

算法思路：

  1. 使用回溯函数，参数包括当前位置、上一个数值、已拆分的段数
  2. 对于每个位置，尝试不同长度的子字符串作为下一段
  3. 检查当前段的数值是否等于上一段数值减1
  4. 递归处理剩余部分
  5. 当处理完整个字符串且至少有2段时，返回true

关键点：

  • 需要处理前导零的情况（如"050"表示数值50）
  • 数值可能很大，需要用长整型存储
  • 剪枝优化：如果当前段数值不等于期望值，直接跳过

推荐解法： 回溯算法是最直观且效率较好的解法，由于字符串长度限制在20以内，时间复杂度可以接受。

代码实现

class Solution {
public:
    bool splitString(string s) {
        return backtrack(s, 0, -1, 0);
    }
    
private:
    bool backtrack(const string& s, int start, long long prev, int count) {
        if (start == s.length()) {
            return count >= 2;
        }
        
        for (int len = 1; len <= s.length() - start; len++) {
            string sub = s.substr(start, len);
            long long curr = stoll(sub);
            
            if (prev == -1 || prev - curr == 1) {
                if (backtrack(s, start + len, curr, count + 1)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def splitString(self, s: str) -> bool:
        def backtrack(start, prev, count):
            if start == len(s):
                return count >= 2
            
            for length in range(1, len(s) - start + 1):
                sub = s[start:start + length]
                curr = int(sub)
                
                if prev is None or prev - curr == 1:
                    if backtrack(start + length, curr, count + 1):
                        return True
            
            return False
        
        return backtrack(0, None, 0)

public class Solution {
    public bool SplitString(string s) {
        return Backtrack(s, 0, -1, 0);
    }
    
    private bool Backtrack(string s, int start, long prev, int count) {
        if (start == s.Length) {
            return count >= 2;
        }
        
        for (int len = 1; len <= s.Length - start; len++) {
            string sub = s.Substring(start, len);
            long curr = long.Parse(sub);
            
            if (prev == -1 || prev - curr == 1) {
                if (Backtrack(s, start + len, curr, count + 1)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

var splitString = function(s) {
    function backtrack(index, prev) {
        if (index === s.length) return true;
        
        for (let i = index; i < s.length; i++) {
            let curr = s.substring(index, i + 1);
            let num = parseInt(curr);
            
            if (prev - num === 1) {
                if (backtrack(i + 1, num)) return true;
            }
        }
        return false;
    }
    
    for (let i = 0; i < s.length - 1; i++) {
        let first = s.substring(0, i + 1);
        let num = parseInt(first);
        if (backtrack(i + 1, num)) return true;
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n)最坏情况下需要尝试所有可能的拆分方式，其中n为字符串长度
空间复杂度O(n)递归调用栈的深度最多为字符串长度