From
Leetcode
Status
AC
Date
Mar 18, 2024
Tags
深度优先搜索
回溯
Difficulty
困难
题面
给你一份航线列表
tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从
JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。- 例如，行程
["JFK", "LGA"]与["JFK", "LGB"]相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1：
示例 2：
提示：
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi和toi由大写英文字母组成
fromi!= toi
思路
首先先把图的邻接表存进字典，然后对字典的value进行排序
然后从'JFK'开始深搜，每前进一层就减去一条路径，
直到某个节点不存通往其他节点的路径时，说明该节点就为此次行程的终点
需要跳出while循环进行回溯，返回到上一层节点进行搜索，再次找到倒数第二个终点，依次类推
设定ans为返回答案，每次找到的节点都要往头部插入
举例说明：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
构建领接表的字典：{'JFK': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})
按照题目要求对字典的val排序：{'JFK': ['ATL', 'SFO'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})
开始从 JFL 开始进行dfs搜索
1.JFK --> ALT
JFK pop出ALT,JFK的字典变为：'JFK': ['SFO']
2.JFK --> ALT --> JFK
ALT pop出JFK,ALT的字典变为：'ALT': ['SFO']
3.JFK --> ALT --> JFK --> SFO
JFK pop出SFO,JFK的字典变为：'JFK': ['']
4.JFK --> ALT --> JFK --> SFO --> ATL
SFO pop出ALT,SFO的字典变为：'SFO': ['']
5.JFK --> ALT --> JFK --> SFO --> ATL --> SFO
ATL pop出SFO,ATL的字典变为：'ATL': ['']
此时我们可以发现SFO的val为空，没有地方可以去了，说明我们已经找出了终点SFO
然后向上回溯，依次将其添加到ans中
最终答案为：["JFK","ATL","JFK","SFO","ATL","SFO"]
由于append效率比insert高，所以可以用逆序