## 题目描述：

LeetCode 332. Reconstruct Itinerary

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:

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 may 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.

## 题目大意：

1. 如果存在多重有效的行程，你应当返回字典序最小的那个。例如，行程["JFK", "LGA"]的字典序比["JFK", "LGB"]要小。
2. 所有的机场用3个大写字母表示（IATA编码）。
3. 你可以假设所有的机票均至少包含一条有效的行程。

## Python代码：

``````class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
routes = collections.defaultdict(list)
for s, e in tickets:
routes[s].append(e)
def solve(start):
left, right = [], []
for end in sorted(routes[start]):
if end not in routes[start]:
continue
routes[start].remove(end)
subroutes = solve(end)
if start in subroutes:
left += subroutes
else:
right += subroutes
return [start] + left + right
return solve("JFK")
``````

## Python代码：

``````class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: 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]
``````

Pingbacks已关闭。

1. Candice 发布于 2016年2月9日 09:19 #

可以解释一下下面这段代码的含义吗？谢谢
for end in sorted(routes[start]):
if end not in routes[start]:
continue

2. 在线疯狂 发布于 2016年2月10日 11:33 #

在遍历sorted(routes[start])过程中，递归调用的子过程可能已经访问并从routes[start]中移除元素，所以添加一个if语句判断下end是否还在routes[start]中。