Leetcode

Backspace String Compare

May 26, 2022 by aAshish

Approach 1: Stack

  • Time:O(n)
  • Space:O(n)

C++

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

JAVA

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

Approach 2: Two Pointers

  • Time:O(n)
  • Space:O(1)

C++

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

JAVA

 
class Solution {
  public boolean 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.charAt(i) == '#' || back > 0)) {
        back += S.charAt(i) == '#' ? 1 : -1;
        --i;
      }
      // delete chars of T if needed
      back = 0;
      while (j >= 0 && (T.charAt(j) == '#' || back > 0)) {
        back += 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;
  }
}

Python

 
class Solution:
  def backspaceCompare(self, S: str, T: str) -> bool:
    i = len(S) - 1
    j = len(T) - 1

    while i >= 0 or j >= 0:
      backspace = 0
      while i >= 0 and (S[i] == '#' or backspace > 0):
        backspace += 1 if S[i] == '#' else -1
        i -= 1
      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] or \
          i < 0 and j >= 0 and S[j] != '#' or \
              j < 0 and i >= 0 and S[i] != '#':
        return False
      i -= 1
      j -= 1

    return True