# [LeetCode] 844. Backspace String Compare 退格字符串比较

2021年09月15日 阅读数：2

Given two strings `S` and `T`, return if they are equal when both are typed into empty text editors. `#` means a backspace character.html

Example 1:java

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

Example 2:python

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

Example 3:c#

```Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
```

Example 4:app

```Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
```

Note:post

1. `1 <= S.length <= 200`
2. `1 <= T.length <= 200`
3. `S` and `T` only contain lowercase letters and `'#'` characters.

• Can you solve it in `O(N)` time and `O(1)` space?

Java: O(1) space
```public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
while (true) {
for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i)
back += S.charAt(i) == '#' ? 1 : -1;
for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j)
back += T.charAt(j) == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
i--; j--;
} else
return i == -1 && j == -1;
}
}
```

Python:spa

``` def backspaceCompare(self, S, T):
i, j = len(S) - 1, len(T) - 1
backS = backT = 0
while True:
while i >= 0 and (backS or S[i] == '#'):
backS += 1 if S[i] == '#' else -1
i -= 1
while j >= 0 and (backT or T[j] == '#'):
backT += 1 if T[j] == '#' else -1
j -= 1
if not (i >= 0 and j >= 0 and S[i] == T[j]):
return i == j == -1
i, j = i - 1, j - 1
```

Python:code

```# Time:  O(m + n)
# Space: O(1)
import itertools

class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
def findNextChar(S):
skip = 0
for i in reversed(xrange(len(S))):
if S[i] == '#':
skip += 1
elif skip:
skip -= 1
else:
yield S[i]

return all(x == y for x, y in
itertools.izip_longest(findNextChar(S), findNextChar(T)))
```

Python: wo O(n) spacehtm

```class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
s1, s2 = [], []
for i in range(len(S)):
if S[i] == '#' and s1:
s1.pop()
elif S[i] == '#':
continue
else:
s1.append(S[i])

for j in range(len(T)):
if T[j] == '#' and s2:
s2.pop()
elif T[j] == '#':
continue
else:
s2.append(T[j])

return s1 == s2
```

C++:

```bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
while (1) {
for (int back = 0; i >= 0 && (back || S[i] == '#'); --i)
back += S[i] == '#' ? 1 : -1;
for (int back = 0; j >= 0 && (back || T[j] == '#'); --j)
back += T[j] == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && S[i] == T[j])
i--, j--;
else
return i == -1 && j == -1;
}
}
```