Show problems as
Classic problem #332HardArrayStringDepth-First SearchGraph TheorySortingHeap (Priority Queue)Eulerian CircuitEulerian PathSemi-Eulerian Graph

Reconstruct Itinerary

Real-world version: Haul Permit Run
Tracked in this browser only
Read Reconstruct Itinerary on LeetCode(opens in a new tab)

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

A regional courier holds a bundle of one-way haul permits. Each permit is written [origin, destination], a pair of three-letter uppercase depot codes, and it entitles the van to drive that leg exactly once. No permit names the same depot twice, and two permits may cover the very same leg, in which case that leg is driven twice.

The van sets out from the depot coded "HUB" and has to spend the whole bundle: every permit is driven exactly once. The bundle is always one that allows this.

Report the run as the list of depot codes the van stands at, in order: "HUB" first, then the destination of each leg as it is driven. The list therefore holds one more code than the bundle holds permits.

Several runs may spend the whole bundle. Return the smallest of them under front-to-back comparison: read two candidate runs position by position from the start, and the one holding the smaller depot code at the first position where they differ is the one to return.

Examples

Example 1

Input
permits = [["HUB", "ARL"], ["HUB", "BEC"], ["BEC", "HUB"]]
Output
["HUB", "BEC", "HUB", "ARL"]

The run drives HUB to BEC, BEC back to HUB, then HUB to ARL, which spends all three permits and stands the van at four depots in turn.

Example 2

Input
permits = [["HUB", "ARL"], ["ARL", "BEC"], ["BEC", "CDR"]]
Output
["HUB", "ARL", "BEC", "CDR"]

Each depot issues a single permit onward, so the bundle chains into one run and there is nothing to compare.

Example 3

Input
permits = [["HUB", "ARL"], ["HUB", "BEC"], ["ARL", "HUB"], ["BEC", "HUB"]]
Output
["HUB", "ARL", "HUB", "BEC", "HUB"]

Two runs spend the bundle: this one and the run that visits BEC before ARL. They first differ at position 1, where ARL is the smaller code.

Constraints

  • 1 <= permits.length <= 300
  • permits[i].length == 2
  • Each depot code is exactly 3 uppercase English letters
  • permits[i][0] != permits[i][1]
  • At least one run starting at "HUB" drives every permit exactly once

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 plan_hauls(permits: list[list[str]]) -> list[str]:
Java
public List<String> planHauls(List<List<String>> permits)

More on the same topics