题目

reconstrcut-itinerary

算法

* multiset

* stack

代码

* multiset

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string> > tickets) {
        vector<string> res;
        unordered_map<string, multiset<string> > m;
        for (auto a : tickets) {
            m[a.first].insert(a.second);
        }
        dfs(m, "JFK", res);
        return vector<string> (res.rbegin(), res.rend());
    }
    void dfs(unordered_map<string, multiset<string> > &m, string s, vector<string> &res) {
        while (m[s].size()) {
            string t = *m[s].begin();
            m[s].erase(m[s].begin());
            dfs(m, t, res);
        }
        res.push_back(s);
    }
};

* stack

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> res;
        stack<string> d;
        unordered_map<string, multiset<string> > m;
        for (auto a : tickets) {
            m[a.first].insert(a.second);
        }
        string cur = "JFK";
        for (int i = 0; i < tickets.size(); ++i) {
            while (m.find(cur) == m.end() || m[cur].empty()) {
                d.push(cur);
                cur = res.back();
                res.pop_back();
            }
            res.push_back(cur);
            string t = cur;
            cur = *m[cur].begin();
            m[t].erase(m[t].begin());
        }
        res.push_back(cur);
        while (!d.empty()) {
            res.push_back(d.top());
            d.pop();
        }
        return res;
    }
};