# 332. Reconstruct Itinerary
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:
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.
# Solution
Approach 1: DFS.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
private:
unordered_map<string,vector<string>> links;
vector<string> res;
bool findRes;
int total;
int cmp(string a, string b) {
for (int i = 0; i < a.size(); ++i)
{
if (a[i] > b[i])
return 1;
else if (a[i] < b[i])
return -1;
}
return 0;
}
void doFindItinerary(string start, vector<string>& path) {
path.push_back(start);
total--;
if (total == 0)
{
res = path;
findRes = true;
}
else
{
for (vector<string>::iterator it = links[start].begin();
it != links[start].end(); ++it)
{
string next = *it;
links[start].erase(it);
doFindItinerary(next, path);
links[start].insert(it, next);
if (findRes)
break;
}
}
path.pop_back();
total++;
}
void doFindItinerary(string start) {
while (links[start].size() > 0)
{
string next = links[start][0];
links[start].erase(links[start].begin());
doFindItinerary(next);
}
res.push_back(start); // Need to be here instead of before while().
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
findRes = false;
total = tickets.size() + 1;
for (int i = 0; i < tickets.size(); ++i)
{
string start = tickets[i][0];
string end = tickets[i][1];
vector<string>::iterator it = links[start].begin();
for (; it != links[start].end(); ++it)
{
if (cmp(*it, end) > 0)
break;
}
links[start].insert(it, end);
}
//vector<string> path;
//doFindItinerary("JFK", path);
doFindItinerary("JFK");
std::reverse(res.begin(), res.end());
return res;
}
};