C++ dfs solution with sorting and a map storing destination index


  • 0

    the unordered_map "next" is used to store the index of the next destination to visit for a departure airport.

        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<string, vector<string>> dests;
            unordered_map<string, int> next;
            for (auto t : tickets) {
                dests[t.first].push_back(t.second);
            }
            for (auto &v : dests) {
                sort(v.second.begin(), v.second.end());
            }
            vector<string> route;
            dfs(dests, next, "JFK", route);
            reverse(route.begin(), route.end());
            return route;
        }
        
        void dfs(unordered_map<string, vector<string>> &dests, unordered_map<string, int> &next, string cur, vector<string>& route) {
            while(next[cur] < dests[cur].size()) {
                dfs(dests, next, dests[cur][next[cur]++], route);
            }
            route.push_back(cur);
        }
    

Log in to reply
 

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