Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

844. Backspace String Compare

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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();
  }
}




			


class Solution {
 public:
  bool backspaceCompare(string S, string T) {
    int i = S.length() - 1;  // S's index
    int j = T.length() - 1;  // T's index

    while (true) {
      // Delete chars of S if needed
      int back = 0;
      while (i >= 0 && (S[i] == '#' || back > 0)) {
        back += S[i] == '#' ? 1 : -1;
        --i;
      }
      // Delete chars of T if needed
      back = 0;
      while (j >= 0 && (T[j] == '#' || back > 0)) {
        back += T[j] == '#' ? 1 : -1;
        --j;
      }
      if (i >= 0 && j >= 0 && S[i] == T[j]) {
        --i;
        --j;
      } else {
        break;
      }
    }

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