We try every possible first number by taking prefixes of the string. Then we check if the rest of the string can be split into consecutive decreasing values.
- For each possible first number (prefix of
s): - Try to match the next consecutive value (first_num - 1) as the next substring.
- Recurse with the remaining string and the next expected value.
- If we reach the end of the string with at least 2 parts, return True.
- Time Complexity: O(N^2) in worst case.
- Space Complexity: O(N).
def split_string(s):
def backtrack(index, prev, count):
if index == len(s):
return count >= 2
num = 0
for i in range(index, len(s)):
num = num * 10 + int(s[i])
if num >= prev:
break
if prev - num == 1 or count == 0:
if count == 0:
if backtrack(i + 1, num, 1):
return True
elif prev - num == 1:
if backtrack(i + 1, num, count + 1):
return True
return False
# Try each possible first number
num = 0
for i in range(len(s) - 1):
num = num * 10 + int(s[i])
if backtrack(i + 1, num, 1):
return True
return False