Reconstruct Itinerary

Medium

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 fromJFK. Thus, the itinerary must begin withJFK.

Note:

  1. 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"] .
  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:

Input: 
[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: 
["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

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

Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

Analysis

By @Grandyang Source: http://www.cnblogs.com/grandyang/p/5183210.html

给一堆飞机票,从中建立一个行程单,如果有多种方法,取其中字母顺序小的那种方法。

本质是有向图的遍历问题,而且本题是关于有向图的边的遍历。

每张机票都是有向图的一条边,我们需要找出一条经过所有边的路径,那么DFS不是我们的不二选择。

步骤

  • 首先把图建立起来,通过邻接链表edge list来建立。但由于题目要求解法按字母顺序小的,这个list可以使用PriorityQueue来自动对存入的节点进行排序。所以edge list 的实现可以是 HashMap<String, PriorityQueue<String>> flights;

  • 然后从节点 "JFK"开始DFS遍历,只要当前节点映射的PriorityQueue里有节点,我们取出这个节点,将其在PriorityQueue里删掉,然后继续递归遍历这个节点,由于题目中限定了一定会有解,那么等图中所有的PriorityQueue中都没有节点的时候,我们把当前节点存入结果中,然后再一层层回溯回去,将当前节点都存入结果,那么最后我们结果中存的顺序和我们需要的相反的。因此也可以在存入结果时,就存入头部(反向插入): path.addFirst(departure);

此外还可以用stack来实现迭代的解法。


其实这里的DFS也是来头不简单:欧拉回路Eulerian Path,Hierholzer算法

Definition: In graph theory, an Eulerian trail (or Eulerian path) is a trial in a finite graph which visits every edge exactly once.

在这里就是每张机票用一次并且全部用掉

一个有向图中存在欧拉路径,iff:

  • 图是连通的,即图上任意二点总有路径连接
  • 满足下面两个条件中的一个:
    • 有且只有一个点的入度比出度少1(作为欧拉路径的起点),有且只有一个点的入度比出度多1(作为终点),且其余点入度 = 出度。
    • 所有点入度 = 出度

已知图中存在欧拉路径,找到一个欧拉路径:

  1. Fleury 算法
  2. Hierholzer 算法

Hierholzer 算法

path = []

DFS(u):
    while (u has unvisited edge e(u,v))
        mark edge e(u, v) as visited
        DFS(v)
    end
    path.pushLeft(u)

回到这个问题,假设n是tickets的数量,那么复杂度

Time:建图:O(n + nlogn), Hierholzer: O(n); Total : O(n + nlogn + n)

Space: O(n)

Solution

DFS + HashMap + Priority Queue : DFS递归有向图遍历 (7 ms, faster than 71.94%)

public class Solution {

    Map<String, PriorityQueue<String>> flights;
    LinkedList<String> path;

    public List<String> findItinerary(String[][] tickets) {
        flights = new HashMap<>();
        path = new LinkedList<>();
        for (String[] ticket : tickets) {
            flights.putIfAbsent(ticket[0], new PriorityQueue<>());
            flights.get(ticket[0]).add(ticket[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);
    }
}

Another implementation with DFS + HashMap + MinHeap (PriorityQueue)

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        LinkedList<String> list = new LinkedList<>();

        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for(String[] ticket : tickets){
            if(!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<String>());

            map.get(ticket[0]).add(ticket[1]);
        }

        dfs(list, "JFK", map);

        return new ArrayList<String>(list);
    }

    private void dfs(LinkedList<String> list, String airport, HashMap<String, PriorityQueue<String>> map){
        while(map.containsKey(airport) && !map.get(airport).isEmpty()){
            dfs(list, map.get(airport).poll(), map);
        }
        list.offerFirst(airport);
    }
}

后话:

这题用DFS的代码,跟Topological Sorting的DFS代码几乎一模一样;也从侧面说明了这道题其实也包含了拓扑排序的内核。

Reference

https://leetcode.com/problems/reconstruct-itinerary/discuss/78766/Share-my-solution

http://www.cnblogs.com/grandyang/p/5183210.html

https://www.youtube.com/watch?v=LKSdX31pXjY

results matching ""

    No results matching ""