[summary] The inspiration from this problem ~


  • 1

    Here the key to this solution is use the data structure

                unordered_map<string, multiset<string>> targets;
    

    First , construct the graph, then we just DFS to traverse the graph and to find the the minimal lexical order

    to use up all the tickets !

    I think the key is that it guarantees that there are enough airports and that it ensures that we have to use up
    all the tickets!

    Here is the solution refered to @StefanPochmann :

    class Solution {
        unordered_map<string, multiset<string>> targets;
        vector<string> route;
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            for(auto ticket : tickets)
                targets[ticket.first].insert(ticket.second);
                
            help("JFK");
            return vector<string>(route.rbegin(), route.rend());
        }
        
        void help(string airport){
            while(targets[airport].size()){
                string next=*targets[airport].begin();
                targets[airport].erase(targets[airport].begin());
                help(next);
            }
            route.push_back(airport);
        }
    };

Log in to reply
 

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