C++ solution using DFS (23 lines, 13 ms)


  • 0
    L
    class Solution {
        unordered_map<string, vector<string>> g;
        unordered_map<string, vector<string>::iterator> its;
        vector<string> tmp;
        void dfs(const string &x) {
            if (g.count(x)) 
                for (auto &it = its[x]; it != g[x].end(); )
                    dfs(*it++);
            tmp.push_back(x);
        }
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            for (const auto &e : tickets)
                g[e.first].push_back(e.second);
            for (auto &it : g) {
                sort(it.second.begin(), it.second.end());
                its[it.first] = it.second.begin();
            }
            dfs("JFK");
            reverse(tmp.begin(), tmp.end());
            return tmp;
        }
    };
    

Log in to reply
 

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