Backspace String Compare

Head on over here to try the problem for yourself.

There are a few ways discussed in the solutions. I will try to explain the two-pointer method.

Algorithm

The goal is to try to build the resultant string in one pass. For this reason, we will iterate over the string backwards. If we encounter #, we simply skip the first valid character that follows. Ofcourse, the caveats are considering more backspaces (#) than actual words, in which case we simply get an empty string. Further, we need a way to handle a series of backspaces and skip an equal number of valid characters.

Code


public boolean backspaceCompare(String s, String t) {
  int skip = 0; // variable to keep track of skips
  int i = s.length() - 1; // iterates over the string in reverse

  StringBuilder s1 = new StringBuilder(); // stores result of s
  StringBuilder s2 = new StringBuilder(); // stores result of t

  char c; // temporarily stores the current character

  while(i >= 0) {
    c = s.charAt(i);
    if(c == '#') skip++; // increment skip to keep track of number of skips
    else {
      if(skip > 0) skip--; // encouters valid character but skip > 0 so decrement skip
      else s1.append(c);
    }
    i--;
  }
  // reset
  skip = 0;
  i = t.length() - 1; 

  while(i >= 0) {
    c = t.charAt(i);
    if(c == '#') skip++;
    else {
      if(skip > 0) skip--;
      else s2.append(c)
    }
    i--;
  }
  // I am comparing the built strings to each other, in reverse :P
  if(s1.toString().compareTo(s2.toString()) == 0) return true; 
  return false;
}