C++ Solution using DFS


  • 12
    Y
      class Solution {
        public:
            vector<string> findItinerary(vector<pair<string, string>> tickets) {
                vector<string> ans;
                int n = tickets.size();
                for(int i = 0; i < n; ++ i){
                    g[tickets[i].first].insert(tickets[i].second);
                }
                dfs("JFK", ans, 1, n);
           //     puts(" -- ");
                reverse(ans.begin(), ans.end());
                return ans;
            }
        private:
            void dfs(string u, vector<string> &ans, int dep, int tot){
                while(g[u].size()){
                    string v = *g[u].begin();
                    g[u].erase(g[u].begin());
                    dfs(v, ans, dep + 1, tot);
                }
                ans.push_back(u);
            }
        private:
        unordered_map<string, multiset<string> > g;
        //unordered_map<string, set<string>::iterator> vis;
        };

  • 3
    S

    Nice solution. However it seems that dep and tot are not useful anymore in your recursion.


  • 0
    Y

    Yep, u r right. Plsz ignore them.


  • 0
    B

    Did you follow the lexical order? I think you should sort "g".


  • 0
    Y

    No ... unordered_map will not sort its data.


  • 1
    J

    multiset will sort its data


Log in to reply
 

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