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

0:00 - Read the problem
4:50 - Drawing Explanation
7:02 - Coding Explanation

leetcode 1849

#python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[poptart-br]

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)

[etherealscaped]

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.

[frida]

*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, '#');

[amegahed]

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

[Mandeepsingh-jocf]

Thank you for your Clear and to the point Explanation.

[VarunMittal-viralmutant]

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)

[cozywind]

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?

[orellavie]

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

[hamsalekhavenkatesh]

wait, on 1:38 how is "89" in descending order? 98 is descending, this is in ascending order ... pls correct me!

[CowCow]

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

[nikhildinesan]

My mind was blank during this ques... couldn't find even a bruteforce soln

[pratyakshyt]

Thank you so much, awesome explanation !!

[entropy]

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

[sunnilabeouf]

Can you do the "Ones and Zeroes" problem?

[jasonswift]

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.

[justinUoL]

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

[nonamenigha]

How many leetcode questions do you solve per day?

[fancyAlex]

There was nothing straightforward about this question lol, I couldn't understand at all.

[kms]

dude, please use cpp or java if possible