[LeetCode] Reconstruct Itinerary - 快车库

Problem

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 ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
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.

Note

来自LC大神@dietpepsi的解答，只能膜拜。
题目确定了至少有一条valid的行程（不存在分支情况，一定有相同的最终目的地），而且对于多条valid的行程，要选取字母顺序较小的一条。重构的行程地点一定是有序的，
所以，使用深度优先搜索，根据departure找到arrivals集合，并利用PriorityQueue对本航段的arrivals进行字母顺序排列，再将排列后的元素顺序取出作为departure，继续DFS，然后一层一层从内而外地将起点departure放入path的首位。

HashMap和LinkedList的两个关键用法如下：

putIfAbsent

Method Detail:

V putIfAbsent(K key, V value)

If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

if (!map.containsKey(key))
       return map.put(key, value);
   else
       return map.get(key);

except that the action is performed atomically.

Parameters:

key - key with which the specified value is to be associated
value - value to be associated with the specified key

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key. (A null return can also indicate that the map previously associated null with the key, if the implementation supports null values.)

addFirst

public void addFirst(E e)

Inserts the specified element at the beginning of this list.

Specified by:

addFirst in interface Deque<E>

Parameters:

e - the element to add

Solution

public class Solution {
    Map<String, PriorityQueue<String>> flights = new HashMap();
    LinkedList<String> path = new LinkedList();
    public List<String> findItinerary(String[][] tickets) {
        for (String[] oneway: tickets) {
            flights.putIfAbsent(oneway[0], new PriorityQueue());
            flights.get(oneway[0]).add(oneway[1]);
        }
        dfs("JFK");
        return path;
    }
    public void dfs(String departure) {
        PriorityQueue<String> arrivals = flights.get(departure);
        while (arrivals != null && !arrivals.isEmpty()) dfs(arrivals.poll());
        path.addFirst(departure);
    }
}