Given two strings S and T, return 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 = "#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?
Simulation Solution
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
return self.str2list(S) == self.str2list(T)
def str2list(self, stri):
ans = []
for c in stri:
if c == '#':
if len(ans) > 0:
ans.pop()
else:
ans.append(c)
return ans
Pointer Solution
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
i = len(S) - 1
j = len(T) - 1
while True:
i = self.move_cursor(S, i)
j = self.move_cursor(T, j)
# Stop condition
if min(i, j) < 0:
if i < 0 and j < 0:
return True
else:
return False
# main logic
if S[i] == T[j]:
i -= 1
j -= 1
continue
else:
return False
def move_cursor(self, S, i):
"""
move cursor i to the position of next char
"""
n_sharp = 0
while i >= 0:
if S[i] == '#':
n_sharp += 1
i -= 1
continue
# S[i] != '#' :
if n_sharp > 0:
i -= 1
n_sharp -= 1
continue
# n_sharp == 0 :
break
return i
self.
while True:
然后中间break,如果发现条件比较清楚的时候再放回正确的位置,如果不能的话就不改了。