Given two strings s and t where # means backspace, return true if the processed strings are equal.
Input: s="ab#c", t="ad#c" → Output: trueInput: s="ab##", t="c#d#" → Output: true
Two pointers from the end of each string. For each string, skip characters that would be deleted by backspace.
- Use two index pointers, one for each string, starting from the end.
- Function nextChar: scan backward, counting # and skipping deleted chars.
- Compare characters at current position; if mismatch return false.
- Return true if both reach beginning together.
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (s.charAt(i) == '#') { skipS++; i--; }
else if (skipS > 0) { skipS--; i--; }
else break;
}
while (j >= 0) {
if (t.charAt(j) == '#') { skipT++; j--; }
else if (skipT > 0) { skipT--; j--; }
else break;
}
if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) return false;
if ((i >= 0) != (j >= 0)) return false;
i--; j--;
}
return true;
}
}
- Time Complexity: O(N+M)
- Space Complexity: O(1)