day9.py

# stupid 10-minute, O(n) space solution bc andrew was hounding me for trying to go straight for the O(1) space solution
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        return self.process(S) == self.process(T)

    # return the list of characters that are typed out in the end
    def process(self, s: str) -> list:
        curr_index, string = 0, []
        
        for char in s:
            if char == '#':
                curr_index = max(0, curr_index - 1)
            else:
                string[curr_index:] = char
                curr_index += 1
      
        return string[:curr_index]
  
# gave up after 50 mins
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        
        s_index, t_index, diff = 0, 0, 0

        while s_index < len(S) or t_index < len(T):
            print(s_index, t_index, diff)
            
            if s_index == len(S):
                if T[t_index] != '#':
                    diff += 1
                t_index += 1
            
            elif t_index == len(T):
                if S[s_index] == '#':
                    diff = max(0, diff - 1)
                else:
                    diff += 1
                s_index += 1
            
            elif S[s_index] == T[t_index]:
                if S[s_index] == '#':
                    diff = max(0, diff - 1)
                    
                s_index = min(len(S), s_index+1)
                t_index = min(len(T), t_index+1)

            elif S[s_index] == '#':
                s_index = min(len(S), s_index+1)
                diff = max(0, diff - 1)
            
            elif T[t_index] == '#':
                t_index = min(len(T), t_index+1)
                diff = max(0, diff - 1)
            
            elif S[s_index] != T[t_index]:
                s_index = min(len(S), s_index+1)
                t_index = min(len(T), t_index+1)
                diff += 1
        
        return diff == 0