Show problems as
Classic problem #2337MediumTwo PointersString

Move Pieces to Obtain a String

Real-world version: Shunting Trolleys Along a Siding
Tracked in this browser only
Read Move Pieces to Obtain a String on LeetCode(opens in a new tab)

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

A single-track siding is written as a string, one character per bay:

  • '<' is a trolley whose brake lets it be pushed only towards the left end;
  • '>' is a trolley whose brake lets it be pushed only towards the right end;
  • '.' is an empty bay.

One push moves a single trolley one bay in its allowed direction. A push is legal only when the destination bay lies on the siding and is empty, so a trolley can never be pushed off an end of the siding and can never be pushed onto an occupied bay.

You are given the current layout start and a wanted layout goal, both of the same length. Return true if some sequence of legal pushes turns start into goal, and false otherwise. Zero pushes is a valid sequence.

Examples

Example 1

Input
start = ".<..>", goal = "<...>"
Output
true

One push takes the `'<'` from bay 1 into the empty bay 0, which is its allowed direction. The `'>'` already sits where the goal wants it.

Example 2

Input
start = "<.>", goal = "<>."
Output
false

The goal asks the `'>'` to end up in bay 1, which is to the left of the bay 2 it starts in, and a `'>'` can only be pushed rightwards.

Example 3

Input
start = "<.", goal = "<<"
Output
false

The goal shows two trolleys while the siding holds one, and a push never adds a trolley.

Constraints

  • 1 <= start.length <= 10^5
  • start.length == goal.length
  • start and goal contain only the characters '<', '>' and '.'.

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 can_shunt(start: str, goal: str) -> bool:
Java
public boolean canShunt(String start, String goal)

More on the same topics