518. Backspace String Compare
Two strings s and t were typed into a very minimal text editor. Each string is a recording of key presses: a lowercase letter means that letter was typed, and a # means the backspace key was pressed, erasing the most recently typed character that is still on screen. Pressing backspace when the screen is already empty does nothing.
Given the two recordings, return true if both leave exactly the same text on screen once every backspace has been applied, and false otherwise.
Follow-up: can you answer in O(n + m) time while using only O(1) extra memory?
Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: In s, the # erases the b, leaving "ac". In t, the # erases the d, also leaving "ac".
Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Every letter in both recordings gets erased, so both screens end up empty.
Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s ends up as "c" while t ends up as "b".
Constraints:
- 1 ≤ s.length, t.length ≤ 200
- s and t consist only of lowercase English letters and '#' characters.
Hints:
Replay the typing: push each letter onto a stack, and on '#' pop the top if the stack is non-empty. The final stacks are the on-screen texts — just compare them.
For the O(1)-space follow-up, walk both strings from the right. Reading backwards, a '#' means "discard the next letter you meet" — keep a per-string skip counter and compare the surviving letters one at a time.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "ab#c", t = "ad#c"
Expected output: true