Sweaty Imposter

Backspace String Compare

EasyStackGrokkingJuniorOpen on LeetCodeUpdated

You're given two strings s and t made of lowercase letters and '#' characters. Each '#' is a backspace that deletes the character typed just before it; a backspace on empty text does nothing. Type each string into its own empty text editor and return true if both editors end up with the same text, and false otherwise.

Examples

s = "ab#c", t = "ad#c" returns true

The backspace removes the b in s and the d in t, so both become "ac".

s = "ab##", t = "c#d#" returns true

Two backspaces in a row erase both letters of s, and t erases each letter right after typing it. Both end up empty.

s = "a#c", t = "b" returns false

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

Constraints

  • 1 <= s.length, t.length <= 200
  • s and t contain only lowercase letters and '#' characters.

Hints

Hint 1

When you hit a backspace, which character does it erase?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

A backspace always removes the most recently typed character still on screen, which is exactly a stack's pop. Replay each string onto its own stack: push every letter, and pop on '#' when the stack is not empty. Then compare the two stacks. In Java a StringBuilder works as the stack. For O(1) extra space, walk both strings from the end with two pointers, counting pending backspaces to skip the characters they erase.

Time

O(n + m)

Space

O(n + m)

Pitfall

Popping on '#' without checking for an empty stack crashes on input like "#a", where the backspace has nothing to delete. A single pass that deletes each letter-then-'#' pair also fails on chains: "ab##" becomes "a#" instead of empty text.

Solutions

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

    private String build(String text) {
        StringBuilder stack = new StringBuilder();
        for (char c : text.toCharArray()) {
            if (c != '#') stack.append(c);
            else if (stack.length() > 0) stack.deleteCharAt(stack.length() - 1);
        }
        return stack.toString();
    }
}
Drill This