26ms C++ solution Backtracking


  • 0
    X
    class Solution {
    public:
        int airports;
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<string, map<string, int>> g;
            for (auto p: tickets) {
                g[p.first][p.second]++;
            }
            vector<string> itinerary;
            airports = tickets.size() + 1;
            dfs("JFK", g, itinerary);
            return itinerary;
        }
        void dfs(const string& airport, unordered_map<string, map<string, int>>& g, vector<string>& itinerary) {
            itinerary.emplace_back(airport);
            for (auto& next: g[airport]) {
                if (next.second > 0) {
                    next.second--;
                    dfs(next.first, g, itinerary);
                    if (itinerary.size() == airports) {
                        return;
                    } else {
                        next.second++;
                    }
                }
            }
            if (itinerary.size() != airports) {
                itinerary.pop_back();
            }
        }
    };
    

Log in to reply
 

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