Backspace String Compare - Leetcode 844 - Python
VloĆŸit
- Äas pĆidĂĄn 27. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đ„· Discord: / discord
đŠ Twitter: / neetcode1
đź Support the channel: / neetcode
â BLIND-75 PLAYLIST: âą Two Sum - Leetcode 1 -...
đĄ DYNAMIC PROGRAMMING PLAYLIST: âą House Robber - Leetco...
Problem Link: leetcode.com/problems/backspa...
0:00 - Read the problem
0:30 - Stack Explanation
2:23 - Two Pointer Explanation
6:29 - Coding Explanation
leetcode 844
#neetcode #leetcode #python
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
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.
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
That follow-up was a nightmare. Thanks for going over it.
Thanks to your roadmap
Okay, wait is over, thanks Navdeep
â€
Could you also explain the problem 1094. Parallel Course 2? not able to understand and mostly people use lru cache instead of implementing dp
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!
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!
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.
There should be a trash btn on the /practice page
@@NeetCodeIO I see it. Thank you. Keep up the good work, super helpful!
Hehe clever neet
I also got stuck at the last test case and hacked my way through while True:
should't we name functon "nextValidIndex" instead of "nextValidChar" ?)
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)
Let's write some neetcode today â€
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
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!
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
@@leeroymlg4692 stack becomes so efficient but I only did it to reduce space
@@jacobsmith538 Thank you
Thatâs O(n) space complexity though right?
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)
cuz of the string, it still counts as o(n)
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)
The space complexity is O(n) here. The optimized code is O(1) space complexity, which requires two pointer algorithm.
@@yasinunlu443 in two pointer approach also the worst case complexity will be O(n)