EasyTwo PointersStringStackSimulation

Backspace String Compare

1 approach, code in every language

You are given two strings s and t, where the character '#' represents a backspace key. Typing a normal character appends it, while typing '#' deletes the character immediately before it (if there is one).

Return true if the two strings produce the same text after all backspaces have been applied, and false otherwise. Note that a backspace on an already-empty text simply does nothing.

A natural solution builds each final string on a stack, but the problem can also be solved in O(1) extra space by scanning both strings from the back and skipping over characters that get deleted.

Example 1

Input: s = "ab#c", t = "ad#c"

Output: true

Both become "ac": in s the b is deleted, and in t the d is deleted.

Example 2

Input: s = "a#c", t = "b"

Output: false

s becomes "c" while t stays "b", so they differ.

Constraints

1 <= s.length, t.length <= 200
s and t contain only lowercase English letters and the '#' character

Build Result With a Stack

Rebuild each final string using a stack, popping on '#', then compare the two results.

Loading animation…

Intuition

Processing backspaces left to right maps cleanly onto a stack: a normal character is pushed, and a '#' pops the most recent character if one exists. After scanning a string, the stack holds exactly the text that would remain after all the deletions. Doing this for both strings gives two clean results, and the answer is just whether those results are identical. This is easy to reason about and hard to get wrong. If you need O(1) extra space instead, you can walk both strings from the right with two pointers, counting pending backspaces to skip deleted characters and comparing surviving characters in place, but the stack version is the most direct to implement.

Algorithm walkthrough

1Write a helper that builds the final text for one string.
2Iterate over the characters: push each normal character onto a stack.
3When a '#' is seen, pop the top character if the stack is non-empty; otherwise ignore it.
4After the scan, the stack (joined into a string) is the processed text.
5Build the processed text for both s and t.
6Return true if the two processed strings are equal, false otherwise.

Implementation

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(string: str) -> str:
            stack = []
            for ch in string:
                if ch == "#":
                    if stack:
                        stack.pop()
                else:
                    stack.append(ch)
            return "".join(stack)

        return build(s) == build(t)

Time

O(n + m)

Space

O(n + m)

n and m are the lengths of s and t. The stack version uses linear extra space; the two-pointer-from-the-back variant reduces this to O(1).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Strike Marks On Two Tapes is our own problem on the technique behind Backspace String Compare: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free