Sharing my 44ms C++ solution


  • 5
    T
    class Solution {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<string, multiset<string>> myGraph;
            int i, n = tickets.size();
            string first, second;
            for(i=0; i<n; i++)
            {
                first  = tickets[i].first;
                second = tickets[i].second;
                myGraph[first].insert(second);
            }
            
            vector<string> marching;
            vector<string> itinerary;
            marching.push_back("JFK");
            
            while(marching.size()>0)
            {
                string from = marching.back();
                if(myGraph.count(from)>0 && myGraph[from].size()>0)
                {
                    multiset<string>& to = myGraph[from];
                    marching.push_back(*to.begin());
                    to.erase(to.begin());
                }
                else
                {
                    itinerary.push_back(from);
                    marching.pop_back();
                }
            }
            
            reverse(itinerary.begin(), itinerary.end());
            return itinerary;
        }
    };

  • 0
    S

    is there maybe a wrong? need to sort myGraph[from] by lexical order ?


  • 0
    T

    the data structure multiset already did the sorting


  • 1
    B

    just curious, can we do this without modify the graph?


  • 0
    S

    May i ask what if the test case is [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"],["ATL","ABC"]].
    In this case , the smallest Itinerary is JFK---ATL---ABC,but you code give the result JFK---ATL---JFK---SFO---ATL---SFO---ABC.
    What's wrong with my understanding?


Log in to reply
 

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