C++ iterative solution with explanation


  • 0
    C

    I implement Hierholzer's algorithm as below.
    unordered_map m keeps record of flights with key as departure and value as a multiset of arrivals. multiset inherently stores arrivals in lexical order. p is denotes where to expand new destinations when the current itinerary gets stuck.

    class Solution {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<string, multiset<string>> m;
            for (int i = 0; i < tickets.size(); i++) {
                m[tickets[i].first].insert(tickets[i].second);
            }
            vector<string> res;
            string pre = "JFK";
            res.push_back(pre);
            int p = 0;
            while (!m.empty()) {
                if (!m[pre].empty()) {
                    string item = *m[pre].begin();
                    res.insert(res.begin() + p + 1, item);
                    m[pre].erase(m[pre].begin());
                    pre = item;
                    p ++;
                }
                else {
                    while (p >= 0) {
                        if (m[res[p]].empty()) p--;
                        else break;
                    }
                    if (p < 0) break;
                    pre = res[p];
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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