Reconstruct Itinerary

hard

Acceptance: 40%

GraphsDFS

Given a collection of flight tickets, each specifying a departure and arrival airport, construct the travel itinerary that uses every ticket exactly once, beginning from 'JFK'. If more than one valid itinerary exists, return the one that is lexicographically smallest.

Examples

Example 1:

Input:tickets = [["JFK","BOS"],["BOS","SFO"],["SFO","JFK"],["JFK","LAX"]]

Output:["JFK","BOS","SFO","JFK","LAX"]

Explanation: All tickets are used in this route, and it is the lexicographically smallest option.

Example 2:

Input:tickets = [["JFK","ATL"],["ATL","JFK"]]

Output:["JFK","ATL","JFK"]

Explanation: The only route uses both tickets.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Reconstruct Itinerary

Examples

Hints

Related Problems