< Back




844. Backspace String Compare

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.