💬 Discord
Sign In
NeetCode #190LC-844EasyTwo Pointers
← Back to All Problems

#190 · #844 · Backspace String Compare(比较含退格的字符串)

📌 Problem Statement & Constraints

Given two strings s and t where # represents a backspace, return whether they are equal after processing all backspaces. A # on an empty text is a no-op. Constraints: 1 <= s.length, t.length <= 200, lowercase letters and #.

💡 Core Algorithmic Approaches

  1. Stack approach: push characters, pop on #. Compare the two resulting stacks. O(n) time and O(n) space.
  2. Two-pointer approach: walk both strings from the end, skipping characters that are logically deleted by counting #s, and compare the surviving characters one at a time.
  3. The two-pointer version achieves O(1) extra space, which is the intended follow-up.
  4. In the two-pointer version, skip counts pending backspaces; while skip > 0, characters are consumed without comparison.

💻 Benchmark Python3 Implementation

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(x: str) -> str:
            st = []
            for ch in x:
                if ch == "#":
                    if st:                 # '#' on empty text is a no-op
                        st.pop()
                else:
                    st.append(ch)
            return "".join(st)

        return build(s) == build(t)


# O(1)-space two-pointer variant
class Solution2:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        while True:
            skip = 0
            while i >= 0 and (skip or s[i] == "#"):
                skip += 1 if s[i] == "#" else -1
                i -= 1
            skip = 0
            while j >= 0 and (skip or t[j] == "#"):
                skip += 1 if t[j] == "#" else -1
                j -= 1
            if i < 0 or j < 0:
                return i == j              # both exhausted
            if s[i] != t[j]:
                return False
            i -= 1
            j -= 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m): each character is processed once in both variants.
💾 Space Complexity
O(n + m) for the stack variant; O(1) for the two-pointer variant.

⚠️ Interview Pitfalls & Follow-ups

  • Popping from an empty stack: # on empty text is a no-op, so the if st: guard is required.
  • Processing the strings forwards in the two-pointer variant: backspaces affect the characters before them, so the scan must go backwards.
  • Forgetting the skip reset between the two strings: each string has its own pending backspace count.
  • Comparing only when both pointers are valid: the final check must confirm that both strings are exhausted simultaneously.