> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Backspace String Compare Python Solution

> Tested Python solution for LeetCode 844 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 844, Easy. Topics: Two Pointers, String, Stack, Simulation. [View on LeetCode](https://leetcode.com/problems/backspace-string-compare/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 844   # by problem number
lcpy gen -s backspace_string_compare   # by problem name
```

## Problem

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.

### Examples

```
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
```

```
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
```

```
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.

**Follow up:** Can you solve it in `O(n)` time and `O(1)` space?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/backspace_string_compare/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/backspace_string_compare/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Walk both strings right-to-left, skipping chars consumed by backspace.
    # Compare next surviving char of each; mismatch or early exhaustion => false.
    # Time: O(n + m)
    # Space: O(1)
    def backspace_compare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        while i >= 0 or j >= 0:
            i = self._next_valid(s, i)
            j = self._next_valid(t, j)
            s_char = s[i] if i >= 0 else ""
            t_char = t[j] if j >= 0 else ""
            if s_char != t_char:
                return False
            i -= 1
            j -= 1
        return True

    def _next_valid(self, text: str, index: int) -> int:
        skip = 0
        while index >= 0:
            if text[index] == "#":
                skip += 1
                index -= 1
            elif skip > 0:
                skip -= 1
                index -= 1
            else:
                break
        return index
```

## Complexity

| Time     | Space |
| -------- | ----- |
| O(n + m) | O(1)  |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).