题目描述
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.
题目大意
字符串数组中包含n个成对出现的字符串，表示从起始地到目的地的机票，要求将所有的机票行程安排起来，前后有序，以“JFK”为起始地，形成一个行程。
（默认一定会找到一个可行的行程，同时若有多个行程安排，按照字典序排列最小的优先）
示例
E1
E2
解题思路
基于DFS的思想，利用map来保存每班飞机的起始地到目的地，递归的过程中依次删除访问过的地点。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)
代码
class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { // 将tickets中的起始地与目的地保存在map中 for(int i = 0; i < tickets.size(); ++i) airl[tickets[i][0]].insert(tickets[i][1]); // DFS递归 dfs("JFK"); // 由于是按逆序保存的，所以返回结果的逆序 return vector<string>(res.rbegin(), res.rend()); } void dfs(string occa) { // 若当前起始地的目的地不为0，则依次访问目的地，并更新目的地，同时递归 while(airl[occa].size()) { string tmp = *airl[occa].begin(); airl[occa].erase(airl[occa].begin()); dfs(tmp); } res.push_back(occa); } private: unordered_map<string, multiset<string> > airl; vector<string> res; };
LeetCode-332 Reconstruct Itinerary
原文：https://www.cnblogs.com/heyn1/p/11201300.html