332. Reconstruct Itinerary (Medium)

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Return ["JFK","ATL","JFK","SFO","ATL","SFO"].

Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution: DFS with stack, recursive

这道题给我们一堆飞机票，让我们建立一个行程单，如果有多种方法，取其中字母顺序小的那种方法。这道题的本质是有向图的遍历问题，那么LeetCode关于有向图的题只有两道Course Schedule和Course Schedule II，而那两道是关于有向图的顶点的遍历的，而本题是关于有向图的边的遍历。每张机票都是有向图的一条边，我们需要找出一条经过所有边的路径，那么DFS不是我们的不二选择。先来看递归的结果，我们首先把图建立起来，通过邻接链表来建立。由于题目要求解法按字母顺序小的，那么我们考虑用multiset，可以自动排序。等我们图建立好了以后，从节点JFK开始遍历，只要当前节点映射的multiset里有节点，我们取出这个节点，将其在multiset里删掉，然后继续递归遍历这个节点，由于题目中限定了一定会有解，那么等图中所有的multiset中都没有节点的时候，我们把当前节点存入结果中，然后再一层层回溯回去，将当前节点都存入结果，那么最后我们结果中存的顺序和我们需要的相反的，我们最后再翻转一下即可，参见代码如下：

version 1: pq priority_queue is faster than multiset

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

version 2: multiset 16ms

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

Solution 2: DFS + iterative

version 1: pq

vector<string> findItinerary(vector<pair<string, string>> tickets) {
    int n = tickets.size();
    vector<string> itinerary(n+1);
    stack<string> dfs;
    map<string, priority_queue<string, vector<string>, greater<string>>> route;
    for (auto& x: tickets) {
        route[x.first].push(x.second);
    }

    string airport;
    dfs.push("JFK");
    int index = n;
    while (!dfs.empty()) {
        string& airport = dfs.top();
        auto& targets = route[airport];
        if (targets.empty()) {
            itinerary[index--] = airport;
            dfs.pop();
        } else {
            dfs.push(targets.top());
            targets.pop();
        }

    }
    return itinerary;
}

version 2: multiset 16ms

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, multiset<string>> m;
        for (auto& a: tickets) m[a.first].insert(a.second);

        stack<string> s; s.push("JFK");
        int idx = tickets.size();
        vector<string> res(idx+1);

        while (!s.empty()) {
            string airport = s.top();
            if (m[airport].empty()) {
                res[idx--] = airport;
                s.pop();
            } else {
                s.push(*m[airport].begin());
                m[airport].erase(m[airport].begin());
            }
        }
        return res;

    }
};