class Solution {
public:
bool splitString(string s) {
}
};
1849. 将字符串拆分为递减的连续值
给你一个仅由数字组成的字符串 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 <= 20s 仅由数字组成原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-05 22:02:11
class Solution:
def splitString(self, s: str) -> bool:
n = len(s)
start = 0
# 枚举第一个子字符串对应的初始值
# 第一个子字符串不能包含整个字符串
for i in range(n - 1):
start = 10 * start + int(s[i])
# 循环验证当前的初始值是否符合要求
pval = start
cval = 0
cidx = i + 1
for j in range(i + 1, n):
if pval == 1:
# 如果上一个值为 1，那么剩余字符串对应的数值只能为 0
if all(s[k] == '0' for k in range(cidx, n)):
return True
else:
break
cval = 10 * cval + int(s[j])
if cval > pval - 1:
# 不符合要求，提前结束
break
elif cval == pval - 1:
if j + 1 == n:
# 已经遍历到末尾
return True
pval = cval
cval = 0
cidx = j + 1
return False
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-05 22:01:37
func splitString(s string) bool {
next:
for i := 1; i < len(s); i++ {
v, _ := strconv.Atoi(s[:i]) // 由于 s 长度至多 20，无需关心是否溢出
v--
for t := s[i:]; t != ""; v-- {
// 移除前导零，但不能全部移除，至少保留一位数字
for len(t) > 1 && t[0] == '0' {
t = t[1:]
}
// 判断 v 是否符合
tmp := strconv.Itoa(v)
if !strings.HasPrefix(t, tmp) {
continue next
}
t = t[len(tmp):]
}
return true
}
return false
}