Backspace String Compare

Share

Given two strings s and t where # means backspace, return true if the processed strings are equal.

Example 1
Input: s="ab#c", t="ad#c" → Output: true
Example 2
Input: s="ab##", t="c#d#" → Output: true

Solution Approach

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.
Java
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)