1. Backspace String Compare (LeetCode)
Model answer
The task
Compare two strings after applying backspaces: each # removes the most recent character when one exists. Return whether the resulting strings are equal.
Key idea
Scan both strings from right to left. Count how many characters each backspace should skip, so the strings can be compared without building their edited versions.
Approach
- Start a pointer at the end of each string.
- For each string, move left while tracking pending backspaces.
- Skip a character if a backspace is pending; otherwise it is the next visible character.
- Compare the next visible characters. If they differ, return
False. - Continue until both strings have no visible characters left, then return
True.
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def next_visible(text: str, index: int) -> tuple[str | None, int]:
"""Return the next character not erased by a backspace, and its index."""
skips = 0
while index >= 0:
if text[index] == "#":
skips += 1
elif skips > 0:
skips -= 1
else:
return text[index], index - 1
index -= 1
return None, -1
i, j = len(s) - 1, len(t) - 1
while i >= 0 or j >= 0:
char_s, i = next_visible(s, i)
char_t, j = next_visible(t, j)
if char_s != char_t:
return False
return True
Complexity:
- Time: O(m + n), where
mandnare the string lengths; each character is visited at most once. - Space: O(1), excluding the helper’s constant-size state.
Common follow-ups
- What if backspace is represented by a different character? Pass it into the helper or replace the
"#"check. - How would you implement this with a stack? Build each edited string by appending ordinary characters and popping on backspace, then compare.
- What happens when a backspace appears with nothing to erase? It is ignored, as handled by the skip count.