2 minutes
Leetcode 844
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;
}