We’re checking to see if two strings are equal after we resolve the backspace character, #. This backspace character removes the preceeding character from the string. The simplest way to solve this is to maintain a stack of characters we’ve seen. If the backspace character appears, we pop the most recently seen character from the stack - if the stack is not empty.
Finally, we join both stack and return the result.
The solution is as follows:
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def resolve(r: str) -> str:
string = []
for c in r:
if c == "#":
if string: string.pop()
else: string.append(c)
return "".join(string)
return resolve(s) == resolve(t)_ Time Complexity:
O(n) - We inspect all characters within the string.
_ Space Complexity:
O(n) - We maintain a stack of characters we’ve seen.