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).