#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-844-backspace-string-compare-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-844-backspace-string-compare-implementation

Repovive

LeetCode 844 Backspace String Compare - Implementation - Coding Patterns I: Arrays, Strings & Hash Maps | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 844 Backspace String Compare - Implementation

The code

Walk both strings backward, skipping characters that get backspaced. Compare valid characters one pair at a time.

function backspaceCompare(s, t):
    i = len(s) - 1
    j = len(t) - 1
    skipS = 0
    skipT = 0
    while i >= 0 or j >= 0:
        while i >= 0:
            if s[i] == '#':
                skipS += 1
                i -= 1
            elif skipS > 0:
                skipS -= 1
                i -= 1
            else:
                break
        while j >= 0:
            if t[j] == '#':
                skipT += 1
                j -= 1
            elif skipT > 0:
                skipT -= 1
                j -= 1
            else:
                break
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return false
        elif i >= 0 or j >= 0:
            return false
        i -= 1
        j -= 1
    return true

$O(n + m)$ time, $O(1)$ space.