10-Backspace-String-Compare.md

Backspace String Compare

Problem Link

https://leetcode.com/problems/backspace-string-compare/

---

Pattern

• Stack
• String

---

Approach

Simulate backspace processing using two pointers from the end for O(1) space.

---

Time Complexity

O(n + m)

Space Complexity

O(1)

---

Java Solution

class Solution {
    private int nextValid(String s, int i) {
        int skip = 0;
        while (i >= 0) {
            if (s.charAt(i) == '#') skip++;
            else if (skip > 0) skip--;
            else break;
            i--;
        }
        return i;
    }

    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        while (i >= 0 || j >= 0) {
            i = nextValid(s, i);
            j = nextValid(t, j);
            if (i < 0 || j < 0) return i == j;
            if (s.charAt(i) != t.charAt(j)) return false;
            i--;
            j--;
        }
        return true;
    }
}