Reconstruct Itinerary
Given a list of tickets, where each ticket is represented as a pair of departure and arrival airports, reconstruct the itinerary in order. All of the tickets belong to a man who departs from "JFK". Thus, the itinerary must start with "JFK". Additionally, if there are multiple possible itineraries, the itinerary with the smallest lexical order should be chosen.
Constraints:
- If there are multiple routes with the same destination, the route with the smallest lexical order should be chosen.
- All of the tickets belong to a man who departs from "JFK".
- The number of tickets is in the range [1, 30000].
Examples:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Explanation: The flight itinerary must start with "JFK" and end with "SJC". The route with the smallest lexical order is chosen.
Solutions
Hierholzer's Algorithm
The solution uses Hierholzer's Algorithm to find the Eulerian path in the graph. The graph is represented as a map where each key is an airport and the value is a list of destinations. The algorithm starts from "JFK" and explores the graph using DFS. The route with the smallest lexical order is chosen by sorting the destinations for each airport.
class Solution {
public: vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> map;
for (auto& ticket : tickets) {
map[ticket[0]].push_back(ticket[1]);
}
for (auto& pair : map) {
sort(pair.second.begin(), pair.second.end());
}
vector<string> res;
dfs(map, "JFK", res, tickets.size() + 1);
return res;
}
private: bool dfs(unordered_map<string, vector<string>>& map, string from, vector<string>& res, int count) {
if (res.size() == count) return true;
if (map.find(from) == map.end() || map[from].empty()) return false;
for (int i = 0;
i < map[from].size();
i++) {
string to = map[from][i];
map[from].erase(map[from].begin() + i);
res.push_back(to);
if (dfs(map, to, res, count)) return true;
res.pop_back();
map[from].insert(map[from].begin() + i, to);
}
return false;
}
}Follow-up:
What if there are multiple possible itineraries with the same lexical order?
