788. Ticket Trail
A courier company hands out one-way tickets. Each entry [from, to] in tickets lets the courier travel from the city from to the city to; city names consist of capital letters and digits. The courier starts in the city "HUB" and must use every ticket exactly once, always leaving from the city where the previous ticket ended. Identical tickets may appear, and every copy must be used.
Return the sequence of cities visited, starting with "HUB"; it has tickets.length + 1 entries. When several valid sequences exist, return the smallest one, comparing the sequences city by city with ordinary string comparison (the first position where they differ decides). The tickets are guaranteed to allow at least one valid sequence.
Example 1
- Input:
- tickets = [["HUB","AA"],["AA","HUB"],["HUB","ZED"]]
- Output:
- ["HUB","AA","HUB","ZED"]
- Explanation:
The courier must come back through AA before using the ticket to ZED, because ZED has no onward ticket and must be last.
Example 2
- Input:
- tickets = [["HUB","B"],["HUB","A"],["A","HUB"]]
- Output:
- ["HUB","A","HUB","B"]
- Explanation:
Going to A first is the smaller choice, and it still leaves a way back to HUB to use the ticket to B.
Example 3
- Input:
- tickets = [["HUB","X"],["X","Y"],["Y","X"]]
- Output:
- ["HUB","X","Y","X"]
- Explanation:
The tickets form one chain: HUB to X, X to Y, then Y back to X.
Constraints
- 1 ≤ tickets.length ≤ 3 * 105
- Each city name has 1 to 6 characters, each a capital letter or a digit
- At least one valid itinerary that starts at
"HUB"and uses every ticket exists
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 300 msC++ 75 msJava 150 msJavaScript 150 msTypeScript 150 ms
Expected complexity
- Time
- O(m log m)
- Space
- O(m)