Show problems as
Classic problem #844EasyTwo PointersStringStackSimulation

Backspace String Compare

Real-world version: Strike Marks On Two Tapes
Tracked in this browser only
Read Backspace String Compare on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTwo Stacks · Stacks & Queues, animated step by step

Two field radios each punch a row of characters onto its own paper tape. A lowercase letter is punched as itself. The character # is a strike mark, and it cancels the nearest letter to its left that no earlier strike mark has already cancelled. A strike mark with no letter left to cancel does nothing at all, and it is never an error.

The reading of a tape is the row of letters that survive, left to right, once every strike mark has been honoured.

Given tapes s and t, return true when the two tapes have the same reading and false otherwise.

Do it in O(1) extra space: work from the cursors you keep, without assembling either reading.

Examples

Example 1

Input
s = "gold#s", t = "gol#ls"
Output
true

Tape `s` loses its `d`, so it reads `gols`. Tape `t` loses its first `l`, then punches `l` and `s`, so it also reads `gols`.

Example 2

Input
s = "note#", t = "not#e"
Output
false

Tape `s` reads `not` and tape `t` reads `noe`, and those two readings differ.

Example 3

Input
s = "pq##", t = "r#w#"
Output
true

The two strike marks on `s` cancel `q` and then `p`, so `s` reads as nothing. Each strike mark on `t` cancels the letter before it, so `t` also reads as nothing.

Example 4

Input
s = "###hive", t = "hive"
Output
true

The three leading strike marks on `s` have no letters to their left, so they do nothing, and both tapes read `hive`.

Constraints

  • 1 <= s.length, t.length <= 200
  • s and t contain only lowercase English letters and the character '#'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def backspace_compare(s: str, t: str) -> bool:
Java
public boolean backspaceCompare(String s, String t)

More on the same topics