Wrong answer and getting confused about "lexical order "


  • 0
    L

    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;
        }
    };

  • 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
    L

    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.