#844
Backspace String Compare
Easy Stack / backwards scan
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In two strings, '#' means backspace. Decide whether they're equal after applying the backspaces.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: are the strings equal after applying '#' as backspace?
Why this works: build each final string with a stack: push letters, pop on '#'.
Example: "ab#c" and "ad#c"
"ab#c" → "ac", "ad#c" → "ac" → true✦Hints open one at a time
A stack (or StringBuilder) handles it: push letters, pop on '#'.
For O(1) space, scan both strings from the end, skipping characters that get erased.
↗Approach
The stack version builds both final strings and compares. The backwards version keeps a skip counter per string and compares the next surviving characters.
</>Solution (Java)
class Solution {
public boolean backspaceCompare(String s, String t) {
return build(s).equals(build(t));
}
private String build(String s) {
StringBuilder sb = new StringBuilder(); // used as a stack
for (char c : s.toCharArray()) {
if (c != '#') sb.append(c);
else if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
}!Common mistake
Popping from an empty stack when the string starts with '#'.
Complexity
- Time: O(n + m).
- Space: O(n + m) with the stack version.
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon