Watch 10 video solutions for Backspace String Compare, a easy level problem involving Two Pointers, String, Stack. This walkthrough by Nick White has 32,325 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Example 1:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".
Example 2:
Input: s = "ab##", t = "c#d#" Output: true Explanation: Both s and t become "".
Example 3:
Input: s = "a#c", t = "b" Output: false Explanation: s becomes "c" while t becomes "b".
Constraints:
1 <= s.length, t.length <= 200s and t only contain lowercase letters and '#' characters.
Follow up: Can you solve it in O(n) time and O(1) space?
Problem Overview: Two strings s and t represent text typed into a text editor where the character # acts as a backspace. Each # deletes the previous character if one exists. The task is to determine whether both strings produce the same final text after applying all backspaces.
Approach 1: Using a Stack to Simulate Typing (O(n) time, O(n) space)
This approach directly simulates how a text editor processes characters. Iterate through each string and push characters onto a stack. When a # appears, pop the top element if the stack is not empty. After processing the entire string, the stack contains the final characters in order. Repeat for both strings and compare the resulting sequences. The key insight is that a stack naturally models backspace behavior because it removes the most recently added character. This method is easy to reason about and mirrors the real typing process, but it requires O(n) additional space to store the intermediate characters. Related concepts appear frequently in stack and string problems where operations modify the most recent element.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimized approach avoids building the final strings entirely. Instead, scan both strings from right to left using two pointers. Maintain a counter that tracks how many characters should be skipped due to backspaces. When a # is encountered, increase the skip counter. When a normal character appears and the counter is positive, decrement the counter and skip the character. This effectively simulates the backspace effect without storing characters. Continue moving both pointers until valid characters are found, then compare them. If the characters differ, the strings are not equal. This approach processes each character at most once, giving O(n) time complexity while using only O(1) extra space. The technique is a strong example of scanning strings efficiently with two pointers and is often categorized under simulation problems.
Recommended for interviews: Start with the stack simulation because it demonstrates a clear understanding of the problem and is straightforward to implement. Then mention the two-pointer optimization. Interviewers usually expect the constant-space solution since it eliminates the need to construct intermediate strings while keeping the same O(n) runtime.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Simulation | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| Two-Pointer Scan from Right | O(n) | O(1) | Preferred in interviews and memory-constrained scenarios since it avoids building new strings. |