Backspace String Compare

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac". s: ab# -> a, then c -> ac. t: ad# -> a, then c -> ac.

Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "". s: ab## -> a# -> "". t: c# -> "", d# -> "".

Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters

Signature

def solution(s: str, t: str) -> bool: ...

Complexity

Time: O(n + m)
Space: O(n + m) or O(1) with two pointers

Hints

Pattern: Stack simulation or two pointers from end
Approach: Stack: Build final string for each, compare. Two pointers: Compare from end, skip characters based on backspace count.
Complexity: Stack: O(n+m) space. Two pointers: O(1) space by processing from right to left

Solutions

Python

def solution(s: str, t: str) -> bool:
    sstack = []
    tstack = []

    for c in s:
        if sstack and c == "#":
            sstack.pop()
        else:
            if c != "#":
                sstack.append(c)

    for c in t:
        if tstack and c == "#":
            tstack.pop()
        else:
            if c != "#":
                tstack.append(c)

    return "".join(sstack) == "".join(tstack)