332.md

332 Reconstruct Itinerary

Description

link

---

Solution

首先这是一道一笔画问题，解决这个问题的方法就是DFS + Greedy，思路如下：

• In Eulerian paths, there must exist a start node(which is JFK in this problem) and a end node.
• End node can be start node or another node.
  • end node is start node iff all nodes has even degree.
  • end node is another node iff there is another odd degree node and start node has an odd degree.

以上就是关于一笔画的描述，我们首先构建一个图包含所有的路径信息，然后从一个节点出发找到end节点，这个end不一定是最终的end节点，如果不是那么一定会有另外一条路径存在于这个end节点中，接着这条路径我们可以继续找到另一个end节点（中间需要删除所有已经遍历过的路径信息（PPS或者说hold这个已经多出来的信息）），同时由于实现DFS过程中保持的PriorityQueue性质，最后得到的一定是按照顺序的答案，详见：

Solution

其实这题最重要的是需要学会使用DFS当中的所谓hold的性质，在循环中我们先处理pop掉的内容，由于对于每一次的dfs都一定会将路径append到答案当中，所以实现了一个暂时hold的效果

---

Code

Complexity T : O(Elog(E)) M : O(E)

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets)[::-1]:
            targets[a] += b,
        route = []
        def visit(airport):
            while targets[airport]:
                visit(targets[airport].pop())
            route.append(airport)
        visit('JFK')
        return route[::-1]