visual walkthrough
Backspace String Compare
Stack simulation, with a two-pointer O(1)-space follow-up.
The idea
Typing the text into a stack mirrors what a keyboard does: letters pile up and '#' removes the top one. Comparing the two final stacks answers the question.
Going backwards lets you skip erased letters without a stack: a '#' tells you how many letters to ignore before the next real one.
Complexity
| approach | time | space |
|---|---|---|
| Type into a stack | O(n) | O(n) |
| Two pointers from the back | O(n) | O(1) |