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