难度: Easy
原题连接
内容描述
Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
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 = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.
Follow up:
Can you solve it in O(N) time and O(1) space?
思路 1
就看一下两个字符串变化完之后是不是相等就行了，
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
def afterChange(s):
res = ''
for i in s:
if i == '#':
res = '' if len(res) == 0 else res[:-1]
else:
res += i
return res
return afterChange(S) == afterChange(T)思路 2
deque
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
q1 = collections.deque()
q2 = collections.deque()
for i in S:
if i != "#":
q1.append(i)
elif q1:
q1.pop()
else:
continue
for i in T:
if i != "#":
q2.append(i)
elif q2:
q2.pop()
else:
continue
return q1==q2Can you solve it in O(N) time and O(1) space?
思路 2
The idea is we first need to find the first char in each string that was not deleted and compare equality.
Corner case is that the number of '#' is larger than the number of chars in front, e.g. "ab#######c" ---> "c"
So in my codes, the outter loop condition is as long as we haven't gone through both strings, we need to keep going. e.g. "ab#########c" vs. "a#c"
The inner loops are to find the next char after deleting.
There are only two cases we need to return False:
1. Both pointers are at a char and these two chars are different.
One pointer is pointing to a char but the other string has been deleted till index 0. i.e.
2. compare a char to an empty string
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
i, poundS = len(S) - 1, 0; j, poundT = len(T) - 1, 0
while i >= 0 or j >= 0:
while i >= 0:
if S[i] == "#":
poundS += 1
elif poundS:
poundS -= 1
else: #found the first undeleted char
break
i -= 1
while j >= 0:
if T[j] == '#':
poundT += 1
elif poundT:
poundT -= 1
else:
break
j -= 1
#either both side are chars then we need to compare
if i >= 0 and j >= 0 and S[i] != T[j]:
return False
#compare a char with empty(have more # than actually char, we delete everything before #)
if (i >= 0) != (j >=0):
return False
i -= 1
j -= 1
return i == j