Backspace String Compare

EASY

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

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

Follow up: Can you solve it in O(n) time and O(1) space?

Approaches

Checkout 2 different approaches to solve Backspace String Compare. Click on different approaches to view the approach and algorithm in detail.

Build Final Strings

This approach simulates the process of typing the characters of each string into a text editor. We can build the final resulting strings for both s and t after processing all the backspace characters. Finally, we compare the two built strings to see if they are identical.

Algorithm

Create a helper function build(String str).
Inside build, initialize an empty StringBuilder.
Iterate through each character of the input string str.
If the character is not '#', append it to the StringBuilder.
If the character is '#' and the StringBuilder is not empty, remove its last character.
After the loop, return the string representation of the StringBuilder.
In the main function, call build(s) and build(t).
Compare the two resulting strings for equality and return the result.

We can write a helper function that takes a string and returns its final version after applying backspaces. This function iterates through the input string and uses a StringBuilder (or a stack) to construct the result.

When a non-backspace character is encountered, it's appended to the StringBuilder.
When a backspace character ('#') is found, if the StringBuilder is not empty, the last character is deleted.
After processing both s and t with this helper function, we get two final strings. The problem then reduces to a simple string comparison.

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 != '#') {
                sb.append(c);
            } else if (sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }
}

Complexity Analysis

Time Complexity: O(N + M), where N and M are the lengths of strings `s` and `t` respectively. We iterate through each string once to build the final strings, and then compare them.Space Complexity: O(N + M). In the worst case (no backspaces), the `StringBuilder`s will store all characters of the original strings, where N and M are the lengths of s and t.

Pros and Cons

Pros:

Conceptually simple and easy to implement.
The logic directly follows the problem description.

Cons:

Requires extra space proportional to the input string lengths, which does not meet the follow-up constraint of O(1) space.

Code Solutions

Checking out 3 solutions in different languages for Backspace String Compare. Click on different languages to view the code.

class Solution {
public
  boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skip1 = 0, skip2 = 0;
    for (; i >= 0 || j >= 0; --i, --j) {
      while (i >= 0) {
        if (s.charAt(i) == '#') {
          ++skip1;
          --i;
        } else if (skip1 > 0) {
          --skip1;
          --i;
        } else {
          break;
        }
      }
      while (j >= 0) {
        if (t.charAt(j) == '#') {
          ++skip2;
          --j;
        } else if (skip2 > 0) {
          --skip2;
          --j;
        } else {
          break;
        }
      }
      if (i >= 0 && j >= 0) {
        if (s.charAt(i) != t.charAt(j)) {
          return false;
        }
      } else if (i >= 0 || j >= 0) {
        return false;
      }
    }
    return true;
  }
}

Video Solution

Watch the video walkthrough for Backspace String Compare

Patterns:

Two Pointers

Data Structures:

StringStack

Companies:

Agoda |Chewy |IBM |Tinkoff |