Backspace String Compare Python

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. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

Using stack :

Time Complexity : O(n) n is larger of both lengths of strings

Space Complexity : O(n)

class Solution:

    def backspaceCompare(self, S: str, T: str) -> bool:

        def build(S):

            stack = []

            for i in S:

                if i == '#' and stack:

                    stack.pop()

                elif i !='#':

                    stack.append(i)

            return ''.join(stack)

        return build(S) == build(T)

Using Two Pointers:

class Solution:

    def backspaceCompare(self, S: str, T: str) -> bool:

        def F(S):

            skip = 0

            for i in reversed(S):

                if i == '#':

                    skip+=1

                elif skip:

                    skip -=1

                else:

                    yield i

        return all(x == y for x,y in itertools.zip_longest(F(S),F(T)))

    

            

Time Complexity : O(n)

Space Complexity : O(1)