-
Notifications
You must be signed in to change notification settings - Fork 7
/
ReconstructItinerary.cpp
40 lines (37 loc) · 1.33 KB
/
ReconstructItinerary.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Problem: https://leetcode.com/problems/reconstruct-itinerary/
#include <string>
#include <vector>
#include <unordered_map>
class ReconstructItinerary {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> ticket_map;
unordered_map<string, vector<string>>::iterator it;
vector<string> result;
for (int i = 0; i < tickets.size(); ++i) {
ticket_map[tickets[i][0]].push_back(tickets[i][1]);
}
for (it = ticket_map.begin(); it != ticket_map.end(); ++it) {
vector<string>& val = it->second;
sort(val.begin(), val.end());
}
string src = "JFK";
DFS(src, ticket_map, result);
std::reverse(result.begin(), result.end());
return result;
}
private:
void DFS(const string& src,
unordered_map<string, vector<string>>& ticket_map,
vector<string>& result) {
if (ticket_map.find(src) != ticket_map.end()) {
vector<string>& destinations = ticket_map[src];
while (destinations.size() > 0) {
string destination = destinations[0];
destinations.erase(destinations.begin());
DFS(destination, ticket_map, result);
}
}
result.push_back(src);
}
};