Wrong answer and getting confused about "lexical order "

  • 0

    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 {
        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
                    route.push_back(vector<string> (1,tickets[i].second));
                } else { //Add destinations on an existed airport
            //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");
            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--) {
                DFS(result.back(), hs,rt,result);
                if (!rt[hs[depart]].size()) return;

  • 0

    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).

  • 0

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

Log in to reply

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