leetcode 332 Reconstruct Itinerary

leetcode 332 Reconstruct Itinerary

Description

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:
1. 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”].
2. All airports are represented by three capital letters (IATA code).
3. 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.

Solution

PS: 用完

n

`class Solution {public: vector findItinerary(vector> tickets) { vector res; if(tickets.empty()) return res; for(auto &r: tickets) mp[r.first].insert({ r.second, false }); res.push_back("JFK"); dfs("JFK", res, tickets.size()); return res; } bool dfs(string from, vector &res, int n) { if((int)res.size() == n + 1) return true; for(auto r = mp[from].begin(); r != mp[from].end(); ++r) { string temp = (*r).first; auto c = mp[from].find({ temp, false }); if(c == mp[from].end()) continue; res.push_back(temp); mp[from].erase(c); mp[from].insert({ temp, true }); if(dfs(temp, res, n)) return true; res.pop_back(); c = mp[from].find({ temp, true }); if(c == mp[from].end()) continue; mp[from].erase(c); mp[from].insert({ temp, false }); } return false; }private: unordered_map>> mp;};`