Splitting a String Into Descending Consecutive Values - Leetcode 1849 - Python

slightly optimized code --> just did a bit more pruning

class Solution:
def splitString(self, s: str) -> bool:
def backtrack(low, lastNum):
for i in range(low, len(s)-1):
split = int(s[low: i+1]);
if (lastNum == '#' or lastNum-1 == split):
if backtrack(i+1, split):
return True;
if lastNum != '#' and int(s[low:]) == lastNum - 1:
return True;
return False;
return backtrack(0, '#');

Woow. I strugled a lot with this problem. Super simple explanation, thank you!

There is far more optimal solution (O(n^2) time and same space complexity (O(n) ). run a loop until half of the size of the string (min 2 numbers to be consecutive), and build all the string below it with a loop and num -1 each time. concatenate all of them to a one string and compare to the input. If equal you found, if not, -1 if you got into half of size

The maximum value of s[:i + 1] exceeds the maximum value of int, so it is wrong to convert s[:i + 1] with int here.

Why do we need two similar loops? the i and j functions? Also it seems one is iterations of initial value, is that correct? Why can't they be written together?

This gave me 95% efficiency
---------------------
def splitString(self, s: str) -> bool:
n = len(s)
def dfs(i, prev):
if i == len(s):
return False

if prev and (prev - int(s[i:]) == 1):
return True

for k in range(i, n):
num = int(s[i:k+1])
if prev is not None and prev - num != 1:
continue
if dfs(k+1, num):
break
else:
return False
return True

return dfs(0, None)

you deserve way more subscribers!!!

Lovely content as usual! Btw, I used a default prev=None and base case check to avoid having to deal with the necessity to have at least one split, and looks like it works too :d
class Solution:
def splitString(self, s: str) -> bool:
def dfs(ind, prev=None):
if ind>=len(s) and prev is not None and len(prev)!=len(s):
return True
for i in range(ind, len(s)):
newPrev = s[ind:i+1]
isValid = prev is None or int(prev)==int(newPrev)+1
if isValid and dfs(i+1, newPrev):
return True
return False
return dfs(0)

Thank you so much

Hi NeetCode, I think your solution cant AC anymore because of this test case "050043".

dude, please use cpp or java if possible

Thank you for your Clear and to the point Explanation.

How did you know this question is asked by Google? I checked the company tags under leetcode and it doesn't show any

leetcode 1849
This question was identified as an interview question from here: @t​

Can you give me the direct github link?

Hi Neetcode do you have backtracking playlist? I find your backtracking code super simple unlike other backtracking code which involves of popping the last element after returning the recursive call.

I was able to solve this by myself. I am so hyped

Can you do the "Ones and Zeroes" problem?