Backspace String Compare
Created: April 9, 2020 by [lek-tin]
Last updated: April 9, 2020
Solution (build string ❌)
Time: O(N)
Space: O(N)
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
res_1 = self.helper(S)
res_2 = self.helper(T)
return len(res_1) == len(res_2) and res_1 == res_2
def helper(self, s):
stack = []
for c in s:
if c != "#":
stack.append(c)
else:
if len(stack) > 0:
stack.pop()
return "".join(stack)
s
Solution (two pointers 👍🏼)
Time: O(N)
Space: O(1)
from itertools import zip_longest
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
return all( a == b for a, b in zip_longest(self.helper(S), self.helper(T)) )
def helper(self, s):
skip = 0
for c in reversed(s):
if c == "#":
skip += 1
elif skip:
skip -= 1
else:
yield c