题目
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.
- One must use all the tickets once and only once.
解题思路
从JFK开始做dfs，每次都先找字典序最小的，并把用过的机票删掉，如果走到一个无法再走的机场，就把他加到结果中，最后的行程单为结果的倒序
代码
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
def dfs(dep):
arr = paths[dep]
while arr:
dfs(arr.pop())
res.append(dep)
res = []
paths = defaultdict(list)
tickets.sort(key=lambda x: x[1], reverse=True)
for s, t in tickets:
paths[s].append(t)
dfs('JFK')
return res[::-1]
