Skip to content

844. Backspace String Compare 👍

Approach 1: Stack

  • Time: $O(|\texttt{s}| + |\texttt{t}|)$
  • Space: $O(|\texttt{s}| + |\texttt{t}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool backspaceCompare(string s, string t) {
    return backspace(s) == backspace(t);
  }

 private:
  string backspace(const string& s) {
    string stack;
    for (const char c : s)
      if (c != '#')
        stack.push_back(c);
      else if (!stack.empty())
        stack.pop_back();
    return stack;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public boolean backspaceCompare(String s, String t) {
    return backspace(s).equals(backspace(t));
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def backspaceCompare(self, s: str, t: str) -> bool:
    def backspace(s: str) -> str:
      stack = []
      for c in s:
        if c != '#':
          stack.append(c)
        elif stack:
          stack.pop()
      return stack

    return backspace(s) == backspace(t)

Approach 2: Two Pointers

  • Time: $O(|\texttt{s}| + |\texttt{t}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  bool backspaceCompare(string s, string t) {
    int i = s.length() - 1;  // s' index
    int j = t.length() - 1;  // t's index

    while (true) {
      // Delete characters of s if needed.
      int backspace = 0;
      while (i >= 0 && (s[i] == '#' || backspace > 0)) {
        backspace += s[i] == '#' ? 1 : -1;
        --i;
      }
      // Delete characters of t if needed.
      backspace = 0;
      while (j >= 0 && (t[j] == '#' || backspace > 0)) {
        backspace += t[j] == '#' ? 1 : -1;
        --j;
      }
      if (i >= 0 && j >= 0 && s[i] == t[j]) {
        --i;
        --j;
      } else {
        break;
      }
    }

    return i == -1 && j == -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1; // s' index
    int j = t.length() - 1; // t's index

    while (true) {
      // Delete characters of s if needed.
      int backspace = 0;
      while (i >= 0 && (s.charAt(i) == '#' || backspace > 0)) {
        backspace += s.charAt(i) == '#' ? 1 : -1;
        --i;
      }
      // Delete characters of t if needed.
      backspace = 0;
      while (j >= 0 && (t.charAt(j) == '#' || backspace > 0)) {
        backspace += t.charAt(j) == '#' ? 1 : -1;
        --j;
      }
      if (i >= 0 && j >= 0 && s.charAt(i) == t.charAt(j)) {
        --i;
        --j;
      } else {
        break;
      }
    }

    return i == -1 && j == -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def backspaceCompare(self, s: str, t: str) -> bool:
    i = len(s) - 1  # s' index
    j = len(t) - 1  # t's index

    while True:
      # Delete characters of s if needed.
      backspace = 0
      while i >= 0 and (s[i] == '#' or backspace > 0):
        backspace += 1 if s[i] == '#' else -1
        i -= 1
      # Delete characters of t if needed.
      backspace = 0
      while j >= 0 and (t[j] == '#' or backspace > 0):
        backspace += 1 if t[j] == '#' else -1
        j -= 1
      if i >= 0 and j >= 0 and s[i] == t[j]:
        i -= 1
        j -= 1
      else:
        break

    return i == -1 and j == -1