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?

Difficulty: introductory

Starter code:

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

Solutions:
class Solution:
    def backspaceCompare(self, S1, S2):
        i1 = len(S1) - 1 
        i2 = len(S2) - 1
        
        while i1 >= 0 or i2 >= 0:
            c1 = ''
            c2 = ''
            if i1 >= 0:
                c1, i1 = self.getChar(S1, i1)
            if i2 >= 0:
                c2, i2 = self.getChar(S2, i2)
            if c1 != c2:
                return False
        return True
        
    
    def getChar(self, s, i):
        char = ''
        count = 0
        while i >= 0 and not char:
            if s[i] == '#':
                count += 1
            elif count == 0:
                char = s[i]
            else:
                count -= 1
            i -= 1
        return char, i



class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        def test(s):
            stack = []
            for l in s:
                if l == '#':
                    if len(stack) != 0:
                        stack.pop()
                else:
                    stack.append(l)
            return ''.join(stack)
                    
        return test(S) == test(T)

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        i, j = len(S) - 1, len(T) - 1
        
        
        backS = backT = 0       
        
        while True:
            while i >= 0 and (backS or S[i] == '#'):
                backS += 1 if S[i] == '#' else -1
                i -= 1
            while j >= 0 and (backT or T[j] == '#'):
                backT += 1 if T[j] == '#' else -1
                j -= 1
            if not (i >= 0 and j >= 0 and S[i] == T[j]):
                return i == j == -1
            i, j = i - 1, j - 1

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        i = len(S) - 1
        j = len(T) - 1
        
        skip_S = 0
        skip_T = 0
        
        while i >=0 or j >= 0:
            while i >=0 and (S[i] == '#' or skip_S > 0):
                if S[i] == '#':
                    skip_S += 1
                else:
                    skip_S -= 1
                i -= 1
                
            while j >=0 and (T[j] == '#' or skip_T > 0):
                if T[j] == '#':
                    skip_T += 1
                else:
                    skip_T -= 1
                j -= 1
                
            if i < 0 and j < 0:
                return True
            elif i >= 0 and j >= 0:
                if S[i] == T[j]:
                    i -= 1
                    j -= 1
                else:
                    return False
            elif i >=0 or j >=0:
                return False
        return True

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        
        s = []
        
        for i in S:
            if i == '#':
                if s:
                    s.pop()
                    
            else:
                s.append(i)
        
        t = []
        
        for i in T:
            if i == '#':
                if t:
                    t.pop()
                    
            else:
                t.append(i)
        
        
        if s == t:
            return True
        
        return False

class Solution:
    


    def backspaceCompare(self, S: str, T: str) -> bool:
        
        def helper(S):
            r = ''
            erase = 0
            for s in S[-1::-1]:
                if s == '#':
                    erase+=1
                elif s !='#' and erase == 0:
                    r=s+r
                elif s !='#' and erase >=1:
                    #r=s+r
                    erase-=1
                
                    
            return r
    
        return helper(S) == helper(T)