Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 844 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 844 # by problem number
lcpy gen -s backspace_string_compare # by problem name
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.
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".
s and t only contain lowercase letters and '#' characters.O(n) time and O(1) space?
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
| Time | Space |
|---|---|
| O(n + m) | O(1) |