Backspace String Compare

The most natural way to solve this is to simulate exactly what happens when you type the strings. We can use a stack: if we see a regular character, we push it onto the stack. If we see a '#', we pop from the stack (if it's not empty). Once we process both strings this way, we just check if the two stacks are identical.

1. 1Create a helper function build(string) that returns the parsed string.
2. 2In build, iterate through characters. Push to stack if it's a letter, pop if it's '#'.
3. 3Return the string representation of the stack.
4. 4Compare build(s) == build(t).

Why it's not optimal: While this is O(n + m) time, it requires O(n + m) space to store the built strings. The follow-up challenges us to do this in O(1) space, which requires two pointers from the end.

def backspaceCompare(s, t):
    def build(string):
        stack = []
        for char in string:
            if char != '#':
                stack.append(char)
            elif stack:
                stack.pop()
        return "".join(stack)
    return build(s) == build(t)

Instead of building the processed strings, scan both from right to left, maintaining skip counters. Whenever we see '#', we increment the skip count. When we see a letter and the skip count is positive, we skip that letter (it was erased).

1. 1Start i = len(s)-1, j = len(t)-1, skip_s = skip_t = 0.
2. 2Advance i leftward: skip '#' chars (increment skip) and erased chars (decrement skip). Stop at the next surviving char.
3. 3Do the same for j.
4. 4Compare the surviving chars at i and j. If they differ, return False. If one is exhausted but not the other, return False.
5. 5Decrement both and repeat. If the loop ends without mismatch, return True.