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.

For example:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes 
"b"

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)