332. 重新安排行程（困难）

思路

由于题目保证了存在一条合法的旅行路线，并要求按照字典序返回完整的路线。该方法通过深度优先搜索和栈的结合，可以保证每次选择字典序最小的终点进行访问，从而得到按照字典序排列的完整旅行路线。 具体来说，首先创建一个无序映射hash，用于存储每个出发地对应的目的地集合。遍历给定的机票列表，将每个出发地和目的地添加到hash中。 接着通过使用栈来模拟递归的过程，可以保证每次都选择字典序最小的终点进行访问。在每次循环中，如果当前终点的终点集合为空，说明已经到达终点，将当前终点插入到结果数组中，并将其从栈中弹出。如果当前终点的终点集合不为空，说明还有未访问的终点，选择其中一个终点压入栈中，并从终点集合中删除。通过这样的方式，可以按照字典序排列完整的旅行路线。 最后，将答案ans进行反转，得到正确的行程路线。

代码

class Solution {
          
   
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
          
   
        unordered_map<string, multiset<string>> hash;
        vector<string> ans;

        for(auto ticket : tickets){
          
   
            hash[ticket[0]].insert(ticket[1]);
        }
        stack<string> s;
        s.push("JFK");
        while(!s.empty()){
          
   
            string next = s.top();
            if(hash[next].empty()){
          
   
                ans.push_back(next);
                s.pop();
            }
            else{
          
   
                s.push(*hash[next].begin());
                hash[next].erase(hash[next].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};