题目
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.
Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
Constraints:
1 <= s.length, t.length <= 200sandtonly contain lowercase letters and'#'characters.
Follow up: Can you solve it in O(n) time and O(1) space?
思路
从右到左遍历两个字符串，当遇到“#”符号时，删去相应的字符，随后对比字符串的值。
智慧算法：遍历字符串的同时，构造结果字符串，正常时复制字符，遇到#时弹出最后一位。
代码
python版本：
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def back(s, p):
count = 0
while p>=0 and count != 0 or s[p] == '#':
count = count+1 if s[p] == '#' else count-1
p -= 1
return p
p1, p2 = len(s)-1, len(t)-1
while p1 >= 0 and p2 >= 0:
# print(p1, p2, s[p1], t[p2])
p1 = back(s, p1)
p2 = back(t, p2)
# print(p1, p2, s[p1], t[p2])
# print()
if (p1 < 0 and p2 >= 0) or (p1 >= 0 and p2 < 0) or p1 >= 0 and p2 >= 0 and s[p1] != t[p2]:
return False
p1 -= 1
p2 -= 1
p1 = back(s, p1) if p1 >= 0 else p1
p2 = back(t, p2) if p2 >= 0 else p2
return True if p1 < 0 and p2 < 0 else False
# 智慧算法。。。
def backspaceCompare(self, S, T):
def back(res, c):
if c != '#': res.append(c)
elif res: res.pop()
return res
return reduce(back, S, []) == reduce(back, T, [])
