Skills101
← All coding problems

Backspace String Compare

easyLinked List & Stack II+10 XPTime limit 2s

Two people type on keyboards where # is the backspace key: it deletes the character just before the cursor (and does nothing if the text is already empty). Given what each person pressed, do they end up with the same text?

Input: two lines, the keys pressed by each person — lowercase letters and #.

Output: true if the final texts are equal, otherwise false.

Constraints: 1 ≤ length of each line ≤ 2·10⁵.

Think about it: a stack gives the final text directly (push letters, pop on #). For O(1) extra memory, scan both strings from the right, counting pending backspaces to skip characters, and compare one surviving character at a time.

Sample input 1

ab#c
ad#c

Sample output 1

true

Sample input 2

a#c
b

Sample output 2

false

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.