回溯4.
首先明确下要求：
所以直接写出如下回溯代码：
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
res = []
path = []
def helper(tickets, used):
for i in range(len(tickets)):
if not path and tickets[i][0] != "JFK":
continue
if used[i]:
continue
if not path or tickets[i][0] == path[-1]:
path.append(tickets[i][1])
used[i] = 1
if len(path) == len(tickets):
res.append(["JFK"]+path.copy())
else:
helper(tickets, used)
used[i] = 0
path.pop()
helper(tickets, [0]*len(tickets))
res.sort(key=lambda x:"".join(x))
return res[0]
很遗憾，这个解法超时了。看了评论区有人说用回溯做出来了，我想我这个解法还有优化空间。当前解法是把所有合理的路径找出来然后排序找出字典序最小的路径，如果能在回溯过程中就把最小路径找出来，也许可以在时间内完成。
一个跑通的解法：
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# defaultdic(list) 是为了方便直接append
tickets_dict = defaultdict(list)
for item in tickets:
tickets_dict[item[0]].append(item[1])
'''
tickets_dict里面的内容是这样的
{'JFK': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})
'''
path = ["JFK"]
def backtracking(start_point):
# 终止条件
if len(path) == len(tickets) + 1:
return True
tickets_dict[start_point].sort()
for _ in tickets_dict[start_point]:
#必须及时删除，避免出现死循环
end_point = tickets_dict[start_point].pop(0)
path.append(end_point)
# 只要找到一个就可以返回了
if backtracking(end_point):
return True
path.pop()
tickets_dict[start_point].append(end_point)
backtracking("JFK")
return path