LeetCode－332. Reconstruct Itinerary

難度:Hard

描述:你會得到一個航空票的列表，其中 tickets[i] = [fromi, toi] 表示一次航班的出發機場和到達機場。按照順序重建行程。

所有的機票都屬於一個從“JFK”出發的人，因此行程必須從“JFK”開始。如果有多個有效的行程，你應該返回在作為單一字符串讀取時具有最小字典順序的行程。

例如，行程["JFK", "LGA"] 的字典順序比["JFK", "LGB"]小。 

你可以假定所有機票至少形成一個有效的行程。你必須使用所有的機票，而且只能使用一次。

方法一 （DFS）：

思路：

1.建立路徑圖(graph)，從起始機場至目標機場。

2.排序目標機場的順序，使每次都以字典順序小的優先走訪。

3.DFS遞迴走訪，起始機場至目標機場，由"JFK"開始。

4.由根部節點機場，即無下一個目標機場，節點加入行程(itinerary)。

5.反轉行程列表，因為行程是在回溯中建立的。

Time Complexity : O( N log N)

Runtime : 15 ms          (89.66%)

Memory : 14.59 MB     (58.51%)

 

class Solution {
public:
    void dfs(string airport, unordered_map<string, priority_queue<string, vector<string>, greater<string>>> &graph, vector<string> &itinerary) {
        while (!graph[airport].empty()) {
            string next_airport = graph[airport].top();
            graph[airport].pop();
            dfs(next_airport, graph, itinerary);
        }
        itinerary.push_back(airport);
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
        for (auto &ticket : tickets) {
            graph[ticket[0]].push(ticket[1]);
        }

        vector<string> itinerary;
        dfs("JFK", graph, itinerary);
        reverse(itinerary.begin(), itinerary.end());
        return itinerary;
    }
};