Backspace String Compare

Easy Arrays & Hashing Two Pointer Original on LeetCode

Backspace String Compare is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers from the end), runs in O(n + m) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (build both strings with a stack) up.

Problem

You are given two strings s and t. Each one describes keys pressed in an empty text editor: a lowercase letter types that letter, and '#' is a backspace that deletes the last typed letter (if the text is empty, it does nothing).

Return true if typing s and typing t produce the same final text, and false otherwise.

Examples

Example 1

Input
s = "xy#z", t = "xw#z"
Output
true
Why
Both strings end up as "xz" after the backspaces are applied.

Example 2

Input
s = "m##n", t = "#n"
Output
true
Why
The second # in s hits an empty editor and does nothing, so both become "n".

Example 3

Input
s = "a#b", t = "b#a"
Output
false
Why
s becomes "b" while t becomes "a".

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (build both strings with a stack)O(n + m)O(n + m)
Optimal (two pointers from the end)O(n + m)O(1)

1Brute force (build both strings with a stack)

TimeO(n + m)Each character is processed once.
SpaceO(n + m)The built strings can be as long as the inputs.

Type each string into a stack: push letters and pop on # when the stack is not empty. Then compare the two results.

  1. build(str): for each character, if it is '#' pop when non-empty, otherwise push.
  2. Return build(s).equals(build(t)).
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

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

2Optimal (two pointers from the end)

TimeO(n + m)Each index of both strings is visited once.
SpaceO(1)Only the pointers and two skip counters.

Walk both strings from right to left. Keep a count of pending backspaces for each: a # increases it, and a letter met while the count is positive is skipped (decreasing the count). When both pointers rest on a surviving letter, those letters must match. The strings are equal when both run out at the same time.

  1. i = s.length - 1, j = t.length - 1.
  2. Loop: move i left to the next surviving letter of s (or -1), the same for j in t.
  3. If both are -1, return true. If only one is -1 or s[i] != t[j], return false.
  4. Decrease i and j and continue.
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        while (true) {
            i = nextLetter(s, i);
            j = nextLetter(t, j);
            if (i < 0 && j < 0) return true;
            if (i < 0 || j < 0 || s.charAt(i) != t.charAt(j)) return false;
            i--;
            j--;
        }
    }

    private int nextLetter(String str, int idx) {
        int skip = 0;
        while (idx >= 0) {
            if (str.charAt(idx) == '#') {
                skip++;
            } else if (skip > 0) {
                skip--;
            } else {
                break;
            }
            idx--;
        }
        return idx;
    }
}

Edge cases to test

  • A backspace on empty text does nothing
  • Both strings become empty (for example "a#" and "##")
  • Several backspaces in a row that delete several letters
  • Strings of different lengths that still produce the same text

Hints

Hint 1

Simulate the typing: a letter is added, # removes the most recent letter if there is one. A stack does exactly that.

Hint 2

Can you avoid building the strings? Read from the back: a # tells you to skip the next letter you meet going left.

Hint 3

Use one pointer per string, starting at the end. Move each to its next surviving letter, compare, and step both.

FAQ

What is the best time complexity for Backspace String Compare?

Optimal (two pointers from the end) runs in O(n + m) time and O(1) extra space. Each index of both strings is visited once.

Which pattern does Backspace String Compare use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Backspace String Compare?

Yes. Brute force (build both strings with a stack) takes O(n + m) time and O(n + m) space. Type each string into a stack: push letters and pop on when the stack is not empty.

Which edge cases should I test for Backspace String Compare?

A backspace on empty text does nothing; Both strings become empty (for example "a" and ""); Several backspaces in a row that delete several letters; Strings of different lengths that still produce the same text.