Tags: "leetcode", "stack", "two-pointers", "generator", access_time 1-min read

Edit this post on Github

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