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.
- One must use all the tickets once and only once.
Example 1:
Input:
[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output:["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:
Input:
[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output:["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]
.
But it is larger in lexical order.
A:
没啥说的, 就是经典的DFS
class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { unordered_map<string, vector<string> > M; for(auto ticket : tickets) M[ticket[0]].push_back(ticket[1]); auto iter = M.begin(); while(iter != M.end()){ sort(iter->second.begin(), iter->second.end()); iter++; } vector<string> res{"JFK"}; dfs(res, M, tickets.size()+1); return res; } private: void dfs(vector<string> &res, unordered_map<string, vector<string> > &M, int total){ string fromCity = res.back(); auto & toCities = M[fromCity]; for(int i = 0;i<toCities.size();i++){ auto toCity = toCities[i]; toCities.erase(toCities.begin() + i); res.push_back(toCity); dfs(res, M, total); if(res.size() == total) return; // we need put back everything and try next position else{ toCities.insert(toCities.begin()+i, toCity); res.pop_back(); } } } };
No comments:
Post a Comment