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:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Using Stack

This problem can be solved using Stack data structure. You can iterate over each character of a string. At the same time, append each character into Stack. If current character is #, you pop the previous character from stack. At the end of the iteration, the stack would contain only characters which are clean after backspace operations.

 1class Solution {
 2    public boolean backspaceCompare(String s, String t) {
 3        return cleanString(s).equals(cleanString(t));
 4    }
 5
 6    private String cleanString(String s) {
 7        Stack<Character> stack = new Stack<>();
 8        for (char c : s.toCharArray()) {
 9            if (c != '#') {
10                stack.push(c);
11            } else if (!stack.isEmpty()) {
12                stack.pop();
13            }
14        }
15        StringBuilder sb = new StringBuilder();
16        return String.valueOf(stack);
17    }
18}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Using StringBuilder

In above solution, we build stack of characters but then we again have to iterate over the stack when using String.valueOf(stack) at the end to build the string. Instead of this, we can use StringBuilder with a variable to keep track of length of the string. StringBuilder acts more like an array of char.

 1class Solution {
 2    public boolean backspaceCompare2(String s, String t) {
 3        return cleanString(s).equals(cleanString(t));
 4    }
 5
 6    private String cleanString (String s) {
 7        StringBuilder sb = new StringBuilder();
 8        int stringLength = 0;
 9        for (char c : s.toCharArray()) {
10            if (c != '#') {
11                sb.append(c);
12                stringLength++;
13            } else if (stringLength > 0) {
14                sb.deleteCharAt(stringLength - 1);
15                stringLength--;
16            }
17        }
18        return sb.toString();
19    }
20}
  • Time Complexity: O(n)
  • Space Complexity: O(n)