• As to the input [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]], I always get ["JFK","KUL","NRT","JFK"] while the expected answer appears to be ["JFK","NRT","JFK","KUL"].

This makes me confused: should "KUL" be lexically smaller than "NRT"? If yes, why the expected answer seeks for "NRT" first? Or did I misunderstood the term as "smallest lexical order"?

My code is put in following, thanks for your kindly input!

``````class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
unordered_map<string, int> hash;
vector<vector<string> > route;
//Step 1: build the graph and sorted in smaller lexical order
int k(0);
for (int i(0);i<tickets.size();i++) {
if (hash.end()==hash.find(tickets[i].first)) { //Add new airport
hash[tickets[i].first]=k;
k++;
route.push_back(vector<string> (1,tickets[i].second));
} else { //Add destinations on an existed airport
route[hash[tickets[i].first]].push_back(tickets[i].second);
}
}
//Step 2: Sort route in lexical decreasing order
for (int i(0);i<route.size();i++) {
sort(route[i].begin(), route[i].end(), lex_comp);
}
//Step 3: DFS
vector<string> result(1,"JFK");
DFS("JFK",hash,route,result);
return result;
}

static bool lex_comp(string str1, string str2) {
return (str1>str2);
}

void DFS(string depart, unordered_map<string, int> &hs, vector<vector<string> > &rt, vector<string> &result) {
int n(rt[hs[depart]].size());
if (!n) return;
for (int i(n-1);i>=0;i--) {
result.push_back(rt[hs[depart]][i]);
rt[hs[depart]].pop_back();
DFS(result.back(), hs,rt,result);
if (!rt[hs[depart]].size()) return;
}
return;
}
};``````

• Your ["JFK","KUL","NRT","JFK"] isn't even valid, as there's no ticket from KUL to NRT (and it's missing the one from JFK to NRT).

• Thank you Stefan. Yeah I overlooked that, must be too sleepy at that time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.