28ms C++ short O(n) solution


  • 1
    class Solution {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
            for (auto& t : tickets) {
                graph[t.first].push(t.second);
            }
            
            vector<string> result(tickets.size() + 1);
            int index = result.size();
            stack<string> dfs;
            dfs.push("JFK");
            while (!dfs.empty()) {
                string& airport = dfs.top();
                auto& targets = graph[airport]; 
                if (targets.size() == 0) {
                    result[--index] = airport;
                    dfs.pop();
                } else {
                    dfs.push(targets.top());
                    targets.pop();
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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