Backspace String Compare - Leetcode 844 - Python

[@user-j5ja95]

I've been refreshing your page everyday for new videos haha thank you for all that you do, if I ever see you in person I'd love to treat you for coffee or yummy food for all the times you helped me prepare for interviews lol

[@lifeofsanjai]

i read through every LC solutions explaining the optimised solution but nothing was helpful. but now you made it clear. thanks a lot man for the explanation.

[@canete_code]

Thanks Neetcode, I've learned a lot from watching your videos, I came up with this solution myself:
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
return self.skipBackspace(s) == self.skipBackspace(t)
def skipBackspace(self, string):
skip = 0
res = ""
for i in range(len(string) -1, -1, -1):
if string[i] == "#":
skip += 1
continue
if skip > 0:
skip -= 1
continue
res += string[i]
return res[::-1]

[@S3aw0lf]

spent over an hour trying to solve for O(1) space complexity even came up with a solution using Ascii value of the strings but the edge cases are making it diffcult so now came to watch ur vid :).Keep up the consistency

[@servantofthelord8147]

That follow-up was a nightmare. Thanks for going over it.

[@cloudx1057]

This is so clear!

[@thetensordude]

Thanks to your roadmap

[@AnnuSharma-mi9lb]

Okay, wait is over, thanks Navdeep
❤

[@rugvedb9842]

I can never really see where to use Stacks. I would have solved this problem in a different way but the stack solution you shared is definitely better!

[@HtotheG]

My advice is that it just comes with practice seeing when to use a stack, queue, heap or other like structure. What helped me the most was using NeetCode's roadmap to see problems that utilize the same datastructures together in a group to try to identify patterns. One pattern for me is that stacks are often used when we want to deal with the element at [i-1] based on some condition at [i]. So in this problem, we might want to delete the previous character based on seeing a '#" in the current character. Hope this helps at all, best of luck!

[@abhinavnair4577]

Here's a simpler version of the code -
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def remove_char(s):
stack = []
for char in s:
if char=='#' and stack:
stack.pop()
elif char!='#':
stack.append(char)
return stack
return remove_char(s)==remove_char(t)

[@yasinunlu443]

The space complexity is O(n) here. The optimized code is O(1) space complexity, which requires two pointer algorithm.

[@abhinavnair4577]

@@yasinunlu443 in two pointer approach also the worst case complexity will be O(n)

[@shreymehra6774]

Could you also explain the problem 1094. Parallel Course 2? not able to understand and mostly people use lru cache instead of implementing dp

[@AngelRojas-iy6yw]

Hi. Is there an option on the neetcode website to reset the roadmap progress? Sometimes I like to start from scratch and I manually un-select all the questions ive done.

[@NeetCodeIO]

There should be a trash btn on the /practice page

[@AngelRojas-iy6yw]

@@NeetCodeIO I see it. Thank you. Keep up the good work, super helpful!

[@GameFlife]

Hehe clever neet

[@naolfekadu6101]

how is it checking the last characters?

[@oniii-chan_]

I also got stuck at the last test case and hacked my way through while True:

[@swastik07]

def func(s):
stack = ''
for i in s:
if stack and i == '#':
stack = stack[:len(stack)-1]
elif i != '#':
stack += i
return stack

return func(s) == func(t)
I have solved it like this

[@jacobsmith538]

This is so much better, I wanted to implement this but I didn't know how to do the subtraction of stack = stack[:len(stack)-1] Thank you!

[@leeroymlg4692]

it would be a little more efficient to use an array as your stack instead of a string because slicing operations on a string isn't as efficient as popping from an array

[@swastik07]

@@leeroymlg4692 stack becomes so efficient but I only did it to reduce space

[@swastik07]

@@jacobsmith538 Thank you

[@Rlh9xc]

That’s O(n) space complexity though right?

[@dohunkim2922]

can anyone comment on this code? works but kinda slow
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def replace_char_at_index(s, index, new_char):
return s[:index] + new_char + s[index + 1:]
def delete(word):
i = 0
flag = 0
while i < len(word):
if word[i] != "#":
if i > flag:
word = replace_char_at_index(word, flag, word[i])
flag += 1
else:
print(flag > 0)
if flag > 0:
flag -= 1
print(word)
i += 1
print(flag)
print()
return word[:flag]
a, b = delete(s), delete(t)
return (a == b)

[@brainstormbalaclava5384]

should't we name functon "nextValidIndex" instead of "nextValidChar" ?)

[@sumitsharma6738]

Let's write some neetcode today ❤

[@swastik07]

Time and space complexity ---- > O(n) and O(1)
def func(s):

ln = 0

stack = ''

for i in s:
if stack and i == '#':

ln -=1
stack = stack[:ln]
elif i != '#':
stack += i

ln += 1

return stack


return func(s) == func(t)

[@sabu4539]

cuz of the string, it still counts as o(n)