LeetCode 332: Reconstruct Itinerary

Explanation:

To reconstruct the itinerary, we can use a depth-first search (DFS) algorithm. We will start from the "JFK" airport and explore all possible flights until we use all the tickets. We will keep track of the visited airports and use a priority queue to ensure that we visit the airports in lexical order. At each step, we will choose the smallest lexical order airport as the next airport to visit.

Algorithm:

1. Create a HashMap to store the list of destinations for each airport.
2. Sort the destinations list in reverse order to get the smallest lexical order.
3. Start the DFS from "JFK" and recursively visit all destinations.
4. Append the airport to the itinerary while backtracking.
5. Return the reversed itinerary as the final result.

Time Complexity:

The time complexity of this algorithm is O(E * log(E)), where E is the number of edges (flights) in the input.

Space Complexity:

The space complexity is O(E) for storing the flights in the HashMap.

:

class Solution {
    Map<String, PriorityQueue<String>> flights;
    List<String> itinerary;

    public List<String> findItinerary(List<List<String>> tickets) {
        flights = new HashMap<>();
        itinerary = new LinkedList<>();

        for (List<String> ticket : tickets) {
            flights.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            flights.get(ticket.get(0)).add(ticket.get(1));
        }

        dfs("JFK");
        return itinerary;
    }

    private void dfs(String airport) {
        PriorityQueue<String> destinations = flights.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll());
        }
        itinerary.add(0, airport);
    }
}