代码随想录算法训练营第三十二天（回溯算法篇）|332. 重新安排行程

学习资料：代码随想录 (programmercarl.com)

332. 重新安排行程

题目链接：332. 重新安排行程 - 力扣（LeetCode）

题目大意

有一份航线列表?tickets?，其中?tickets[i] = [fromi, toi]?表示飞机出发和降落的机场地点。对该行程进行重新规划排序。所有这些机票都属于一个从?JFK（肯尼迪国际机场）出发的先生，所以该行程必须从?JFK?开始。如果存在多种有效的行程，按字典排序返回最小的行程组合。

思路

1. 出发/目的地机场的映射关系

可以运用字典，直接将出发机场和目的地机场关联，这样就不用运用序列方式先确定出发机场一样，再找到对应的目的地机场（e.g ticket[0] == curAirport --> append(ticket[1]).

2.?字母序靠前排在前面

和之前的增序子列相似，先将列表排序，这样一旦找到，就肯定是靠前的那个。

代码实现

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets):
        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系
        for ticket in tickets:
            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中
        
        for key in targets:
            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序     
        result = []
        self.backtracking("JFK", targets, result)  # 调用回溯函数开始搜索路径
        return result[::-1]  # 返回逆序的行程路径
    
    def backtracking(self, airport, targets, result):
        while targets[airport]:  # 当当前机场有可到达的目的地机场
            next_airport = targets[airport].pop()  # 弹出下一个机场
            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索
        result.append(airport)  # 将当前机场添加到行程路径中