'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
import itertools


class Solution:
    # educative.io 
    # T: O(M+N), lengths of S and T
    # S: O(1)
    def backspaceCompare3(self, S, T):

        def get_nxt_char(string, idx):
            # it's actually reverse iterating
            ct = 0 # ct of #
            while idx >= 0:
                if string[idx] == "#":
                    ct += 1
                elif ct > 0:
                    ct -= 1
                else: # ct == 0
                    break
                idx -= 1
            return idx

        ptr1 = len(S) - 1
        ptr2 = len(T) - 1
        while ptr1 >= 0 or ptr2 >= 0:
            idx1 = get_nxt_char(S, ptr1)
            idx2 = get_nxt_char(S, ptr2)
            if idx1 < 0 and idx2 < 0:
                return True
            if idx1 < 0 or idx2 < 0:
                return False
            if S[idx1] != T[idx2]:
                return False
            ptr1 = idx1 - 1
            ptr2 = idx2 - 1
        return True


    # O(1) space, two pointer
    def backspaceCompare2(self, S, T):
        def F(S):
            skip = 0
            for x in reversed(S):
                if x == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else: # skip == 0
                    yield x                
        # zip_longest fillvalue default as None
        return all(x == y for x, y in itertools.zip_longest(F(S), F(T)))
    
    
    # self-made, not O(1)
    def backspaceCompare(self, S: str, T: str) -> bool:
        def helper(string):
            res = ""
            if not string: return res
            for c in string:
                if c == "#":
                    res = res[:-1] if res else res
                else:
                    res += c
            return res
                    
        s = helper(S)
        t = helper(T)
        return s == t
        
    
    # little bit fancier, T and S: O(M+N), M = len(S) and N = len(T)
    def backspaceCompare1(self, S, T):
        def build(S):
            ans = []
            for c in S:
                if c != '#':
                    ans.append(c)
                elif ans:
                    ans.pop()
            return "".join(ans)
        return build(S) == build(T)