Backspace String Compare
Easy · Two Pointers · Two Pointers · String · Stack · Simulation
Problem
You are given two strings s and t as they were typed into two separate text editors. The character # stands for a backspace key press, which deletes the character before the cursor if there is one; a backspace in an empty editor does nothing.
Return true if both editors end up showing the same text.
Follow-up: solve it in O(n) time with O(1) extra space.
Examples
Input: s = "xy#z", t = "xzz#" Output: true
Both editors end up showing "xz".
Input: s = "a##b", t = "#b" Output: true
Extra backspaces in an empty editor are ignored, leaving "b" in both.
Input: s = "ab#c", t = "ac#b" Output: false
The results are "ac" and "ab".
Constraints
- 1 <= len(s), len(t) <= 200
- s and t contain only lowercase letters and #
Approaches
- Baseline: type both strings with a stack — time O(n + m), space O(n + m)
Follow-up
Suppose the editors also had a key that deletes the whole previous word. Does the right-to-left scan still work with O(1) memory? What would the skip counter have to count?
Related problems
Start free on Cariara · Coding problems · System design studio
