Problem:
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.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
Idea:
Convert the graph to a tree and do post-order traversal
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua // Running time: 13 ms class Solution { public: vector<string> findItinerary(vector<pair<string, string>> tickets) { route_.clear(); trips_.clear(); for(const auto& pair : tickets) trips_[pair.first].push_back(pair.second); for(auto& pair : trips_) { auto& dests = pair.second; std::sort(dests.begin(), dests.end()); } const string kStart = "JFK"; visit(kStart); return vector<string>(route_.crbegin(), route_.crend()); } private: // src -> {dst1, dest2, ..., destn} unordered_map<string, deque<string>> trips_; // ans (reversed) vector<string> route_; void visit(const string& src) { auto& dests = trips_[src]; while (!dests.empty()) { // Get the smallest dest const string dest = dests.front(); // Remove the ticket dests.pop_front(); // Visit dest visit(dest); } // Add current node to the route route_.push_back(src); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment