题目描述
题目链接:332. Reconstruct Itinerary
You are given a list of airline
tickets
wheretickets[i] = [fromi, toi]
represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.All of the tickets belong to a man who departs from
"JFK"
, thus, the itinerary must begin with"JFK"
. 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"]
. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
例子
例子 1
Input:
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output:["JFK","MUC","LHR","SFO","SJC"]
例子 2
Input:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output:["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation:Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]
but it is larger in lexical order.
Constraints
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi
andtoi
consist of uppercase English letters.fromi != toi
解题思路
这道题的思路分为两部分,首先是构建图,然后通过深度优先搜索找到一条路径使其可以遍历所有的城市(使用完所有机票)。这里有两点要注意:由于票是可以重复的,所以要用整数来标记还没使用的票数而不是布尔值来标记是否使用过;有可能有超过一条路径可行,此时需要选择字母序最小的,因此存储路径的时候可以使用map
而不是经常使用的unordered_map
来存储目的地。
代码如下:
#include <map>
#include <string>
#include <unordered_map>
#include <vector>
class Solution {
public:
std::vector<std::string> findItinerary(
std::vector<std::vector<std::string>>& tickets) {
total_count = tickets.size() + 1;
graph g;
for (auto ticket : tickets) {
g[ticket[0]][ticket[1]]++;
// g[ticket[0]].insert({ticket[1], false});
}
std::string curr = "JFK";
std::vector<std::string> ans{curr};
int count = 1;
dfs(g, curr, ans, count);
// cout << endl;
return ans;
}
private:
int total_count;
using graph = std::unordered_map<std::string, map<std::string, int>>;
void dfs(graph& g, std::string& curr, std::vector<std::string>& ans,
int& count) {
std::string next = "";
// cout << "\ncurr: " << curr << " ";
for (auto city : g[curr]) {
if (city.second == 0) continue;
next = city.first;
g[curr][next]--;
ans.push_back(next);
count++;
// cout << next << ", ";
dfs(g, next, ans, count);
// cout << "rechoosing.. \n";
if (count == total_count) return;
count--;
ans.pop_back();
g[curr][next]++;
}
}
};
- 时间复杂度: TBD
- 空间复杂度: TBD
GitHub 代码同步地址: 332.ReconstructItinerary.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions