-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem332.py
101 lines (78 loc) · 2.99 KB
/
problem332.py
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
'''
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:
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"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:
Input: [["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.
Solution:
This has a tricky requirement, that the traveller has to start at JFK.
Use topological sort in this, along with dfs. Or we can say that topological sort is implemented
by dfs.
Read the code again and carefully, we should get this.
From 1/29/2020:
Actually this is not so right about the solution.
How the popleft works? Cause there is no redundent tickets in the collection, every ticket would
definitely be used, and only used once. That's why when we perform a dfs, simply use popleft could
give us a correct path to reconstruct the itinerary.
'''
'''
class Solution(object):
def findItinerary(self, tickets):
locations = []
for i in tickets:
locations.append(i[0])
locations.append(i[1])
locations = list(set(locations))
locations_dict = {}
for i,location in enumerate(locations):
locations_dict[location] = i
for i in tickets:
i[0] = locations_dict[i[0]]
i[1] = locations_dict[i[1]]
grid = [[0 for i in range(len(locations))] for i in range(len(locations))]
for i in tickets:
grid[i[0]][i[1]] = 1
print tickets
start = locations_dict['JFK']
def rec_dfs(graph, start, visited = None):
if visited == None:
visited = []
visited.append(start)
for next in graph[start] - visited:
rec_dfs(graph, next, visited)
return visited
rec_dfs(grid,0)
'''
from collections import defaultdict,deque
class Solution(object):
def _DFS(self, graph, node):
neighbors = graph[node]
while neighbors:
nei = neighbors.popleft()
self._DFS(graph, nei)
self.itinerary.append(node)
def _makeGraph(self, edges):
graph = defaultdict(deque)
for e in edges:
graph[e[0]].append(e[1])
return graph
def findItinerary(self, tickets):
tickets.sort(key= lambda x: x[1])
graph = self._makeGraph(tickets)
self.itinerary = []
self._DFS(graph, "JFK")
return self.itinerary[::-1]
if __name__ == '__main__':
s = Solution()
airlines = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
print s.findItinerary(airlines)