Backspace String Compare

Problem

Given two strings, return true iff they become equal after typing them into an editor where "#" means backspace.

Constraints

• 1 ≤ s.length, t.length ≤ 200

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def backspaceCompare(self, s, t):
        def build(x):
            st = []
            for c in x:
                if c == '#':
                    if st:
                        st.pop()
                else:
                    st.append(c)
            return st
        return build(s) == build(t)

Java

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return apply(s).equals(apply(t));
    }
    private String apply(String s) {
        StringBuilder b = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '#') { if (b.length() > 0) b.deleteCharAt(b.length() - 1); }
            else b.append(c);
        }
        return b.toString();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.