Question:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary

1.[“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

2.All airports are represented by three capital letters (IATA code).

3.You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

Return

["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Return

["JFK","ATL","JFK","SFO","ATL","SFO"].

Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

Thinking:

We need to use dfs to travse all the graph and record the graph. But we need to record it in order. So it should be stored in PriorityQueue and store the route while visiting. If it’s stuck we back up but also record the previous information, because we know there are other ways to get there. Until all the edges are visited once, it’s finished.

Solution:

List<String> res = new ArrayList<String>();
HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();

public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket: tickets)
        map.computeIfAbsent(ticket[0], k -> new PriorityQueue<String>()).add(ticket[1]);
    visit("JFK");

    return res;
}

private void visit(String cur) {
    while (map.containsKey(cur) && !map.get(cur).isEmpty())
        visit(map.get(cur).poll());
    res.add(0, cur);
}

Reference: https://leetcode.com/discuss/84659/short-ruby-python-java-c