Сложность: easy
Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.
Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.
Пример:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
👨💻 Алгоритм:
1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы.
2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены.
3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false.
😎 Решение:
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
i, j = len(S) - 1, len(T) - 1
skipS = skipT = 0
while i >= 0 or j >= 0:
while i >= 0:
if S[i] == '#':
skipS += 1
i -= 1
elif skipS > 0:
skipS -= 1
i -= 1
else:
break
while j >= 0:
if T[j] == '#':
skipT += 1
j -= 1
elif skipT > 0:
skipT -= 1
j -= 1
else:
break
if i >= 0 and j >= 0 and S[i] != T[j]:
return False
if (i >= 0) != (j >= 0):
return False
i -= 1
j -= 1
return True
Ставь 👍 и забирай 📚 Базу знаний