Backspace String Compare

Solution

Simulation

class Solution:
    def sim(self, s):
        res = []
        for c in s:
            if c == '#':
                if len(res): res.pop()
            else:
                res.append(c)
        return res

    def backspaceCompare(self, s: str, t: str) -> bool:
        # simulation
        res_s = self.sim(s)
        res_t = self.sim(t)
        print(res_s)
        print(res_t)
        return res_s == res_t

Two Pointers

Iterate through the string in reverse. If we see a backspace character, the next non-backspace character is skipped. If a character isn't skipped, it is part of the final answer.

def backspaceCompare(self, s: str, t: str) -> bool:
    # simulation
    skip_s = skip_t = 0
    i = len(s) - 1
    j = len(t) - 1

    while i >= 0 or j >= 0:
        while i >= 0:
            if s[i] == '#': # can skip next char
                skip_s += 1
                i -= 1
            elif skip_s > 0: # skip char
                skip_s -= 1
                i -= 1
            else: # char is not skipped
                break

        while j >= 0:
            if t[j] == '#': # can skip next char
                skip_t += 1
                j -= 1
            elif skip_t > 0: # skip char
                skip_t -= 1
                j -= 1
            else: # char is not skipped
                break
        
        # compare two diff chars
        if i >= 0 and j >= 0 and s[i] != t[j]:
            return False
        # compare a char and nothing
        if (i >= 0) != (j >= 0):
            return False
        i -= 1
        j -= 1
    return True