Backspace String Compare

Intuition

Processing backspaces left to right maps cleanly onto a stack: a normal character is pushed, and a '#' pops the most recent character if one exists. After scanning a string, the stack holds exactly the text that would remain after all the deletions. Doing this for both strings gives two clean results, and the answer is just whether those results are identical. This is easy to reason about and hard to get wrong. If you need O(1) extra space instead, you can walk both strings from the right with two pointers, counting pending backspaces to skip deleted characters and comparing surviving characters in place, but the stack version is the most direct to implement.

Algorithm walkthrough

1. 1Write a helper that builds the final text for one string.
2. 2Iterate over the characters: push each normal character onto a stack.
3. 3When a '#' is seen, pop the top character if the stack is non-empty; otherwise ignore it.
4. 4After the scan, the stack (joined into a string) is the processed text.
5. 5Build the processed text for both s and t.
6. 6Return true if the two processed strings are equal, false otherwise.

Implementation

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(string: str) -> str:
            stack = []
            for ch in string:
                if ch == "#":
                    if stack:
                        stack.pop()
                else:
                    stack.append(ch)
            return "".join(stack)

        return build(s) == build(t)