Backspace String Compare
Two Pointers
Problem
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.
Solution
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
i = len(S)-1
j = len(T)-1
backSpaceS = 0
backSpaceT = 0
while i >= 0 or j >= 0:
while i >= 0:
if S[i] == '#':
backSpaceS+=1
i-=1
elif S[i] != '#' and backSpaceS > 0:
i-=1 #'deleting' the next character by skipping it
backSpaceS-=1
else:
break
while j >= 0:
if T[j] == '#':
backSpaceT+=1
j-=1
elif T[j] != '#' and backSpaceT > 0:
j-=1
backSpaceT-=1
else:
break
if S[i] != T[j]:
return False
#this checks if all the elements of one string is deleted but not the
#other
if (i < 0 and j >= 0) or (j < 0 and i >= 0):
return False
i-=1
j-=1
print(i,j)
return True
#inner while loop main purpose is to check for
#backspaces and control the deletion
#Time: O(N+M)
#Space: O(1)
PreviousSort Colors (Dutch National Flag Problem)NextShortest Unsorted Continuous Subarray (Minimum Window Sort)
Last updated
Was this helpful?