1def backspace_compare(s, t):
2 def next_valid(string, index):
3 backspaces = 0
4 while index >= 0:
5 if string[index] == '#': backspaces += 1
6 elif backspaces > 0: backspaces -= 1
7 else: break
8 index -= 1
9 return index
10 i, j = len(s) - 1, len(t) - 1
11 while i >= 0 or j >= 0:
12 i = next_valid(s, i); j = next_valid(t, j)
13 if i >= 0 and j >= 0 and s[i] != t[j]: return False
14 if (i >= 0) != (j >= 0): return False
15 i -= 1; j -= 1
16 return True