难度 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 仅由数字组成
解题思路：这道题目是2021年5月2日参与力扣周赛的第二道题，我提交了13遍才通过，可以说是非常失败了。各种修修补补，没有考虑edge case，每次都是出现一个新case之后才考虑怎么修改，唉，这样下去没救了。
说一下解决的思路，这里用的是dfs，接近暴力解法吧，就是从头遍历数组，组成第一个数cur，遍历的范围显然最多就只能到数组长度的一半加一,也就是s.length()+1，对应把字符串分为两个数这种情况。然后在剩下的字符串s里找是否有cur-1，这就回到第一个情境，所以这就是一个递归函数，递归函数的参数就是字符串剩下的部分s和我们要在字符串中查找的下一个数cur，当递归的过程中，如果s的长度为0，说明前面的递归函数都满足，此时已经到达原始字符串的终点，因此所有的数都已经找到了，直接返回true；否则的话我们就要在剩下的字符串继续寻找cur,我们可以用s.indexOf(String.valueOf(cur))==0这种方法来判断，注意我们需要对字符串做一个处理，去掉字符串开头所有的0，因此我们保证每次查找的cur的index必须为0，否则就是不满足。这样就带来另一个case，那就是‘10’这种情况，进入递归函数的时候s="0", cur=0，这种情况下我们去零的操作会导致结果出错，因此我们考虑当要找的数cur为0且s刚好全为0的情况，这种情况应该返回true，其他情况都是返回false；还有一个需要注意的点是我们用Integer.parseInt的时候数值会越界，因此我们需要使用Long.parseLong来进行字符串与数字的转换。最后一个edge case就是，当s去掉0之后为空字符串或长度为1，也需要返回false，否则会出错。
代码 t100 s100 java
class Solution {
public boolean splitString(String s) {
int i = 0;
long cur = 0;
while(i<s.length() && s.charAt(i)==‘0‘) i++;
s = s.substring(i);
if(s.length()==0 || s.length()==1) return false;
for(int j=1; j<=s.length()/2+1; j++){
cur = Long.parseLong(s.substring(0, j));
if(helper(s.substring(j), cur-1)) return true;
}
return false;
}
public boolean helper(String s, long cur){
if(s.length()==0) return true;
if(cur==0 && Long.parseLong(s)==0) return true;
int i=0;
while(i<s.length() && s.charAt(i)==‘0‘) i++;
s = s.substring(i);
int idx = s.indexOf(String.valueOf(cur));
// System.out.println(idx);
if(idx!=0) return false;
return helper(s.substring(String.valueOf(cur).length()), cur-1);
}
}
下面贴的这个代码更加简洁，思路是一样的。
代码 t100 s100 java
class Solution {
public boolean splitString(String s) {
long cur=0;
for(int i=0;i<s.length()-1;i++){
cur=cur*10+s.charAt(i)-‘0‘;
if(dfs(s.substring(i+1),cur)){
return true;
}
}
return false;
}
private boolean dfs(String s,long max){
long cur=0;
for(int i=0;i<s.length();i++){
cur=cur*10+s.charAt(i)-‘0‘;
}
if(cur==max-1){
return true;
}
cur=0;
for(int i=0;i<s.length();i++){
cur=cur*10+s.charAt(i)-‘0‘;
if(cur<max-1){
continue;
}else if(cur>max-1){
break;
}
if(dfs(s.substring(i+1),cur)){
return true;
}
}
return false;
}
}
原文：https://www.cnblogs.com/zhengxch/p/14725970.html