给你一个仅由数字组成的字符串 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 = “10009998”
输出:true
解释:s 可以拆分为 [“100”, “099”, “98”] ,对应数值为 [100,99,98] 。
满足按降序排列,且相邻值相差 1 。
提示:
1 <= s.length <= 20
s 仅由数字组成链接:https://leetcode-cn.com/problems/splitting-a-string-into-descending-consecutive-values
思路:
因为最长20位,暴力枚举所有分法,每次计算分法是否满足要求最坏复杂度 能过
详见代码
/*
* @Author: ACCXavier
* @Date: 2021-05-08 20:49:11
* @LastEditTime: 2021-05-09 23:22:09
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://leetcode-cn.com/problems/splitting-a-string-into-descending-consecutive-values/
* @keywords:
*/
class Solution {
public:
bool splitString(string s) {
int n = s.size();
//n位的分法是2^(n-1)种,因为缝隙只有n-1个
for(int i = 1; i < (1<<n-1); ++ i){//由于必须要分,所以从i=1即00..01分法开始
unsigned long long last = -1,x = s[0] - '0';//last表示上一个分出来的区间的值,x表示当前区间的值,最大可能是19位数,可能会爆ll,故使用ull
//longlong最大9,223,372,036,854,775,808(19位)如果出现19个9就会爆
//上面x已经有了第一位的值是因为分割线夹在两个数之间,枚举第一个分割线的时候计算会用到0位置的值
//i的二进制表示分法
bool flag = true;//当前分法是否可行
for(int j = 0; j < n -1 ;j ++){
if(i >> j & 1){//为1说明j处有分割线
if(last!=-1&&x != last - 1){
flag = false;
break;
}
//当前区间分割成功
last = x;
x = s[j + 1] - '0';//进入下一个区间
}else{
x = x * 10 + s[j + 1] - '0';//计算x 注意j后移一位
}
}
//最后要判断
if(x !=last - 1)flag = false;
if(flag)return true;
}
return false;
}
};