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.

[@hyperboliq]

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

[@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

[@thetensordude]

Thanks to your roadmap

[@cloudx1057]

This is so clear!

[@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]

[@shivambarke]

Good Solution but it still is of O(s+t) space complexity

[@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

[@naolfekadu6101]

how is it checking the last characters?

[@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!

[@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?

[@GameFlife]

Hehe clever neet

[@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" ?)

[@oniii-chan_]

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

[@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)