reconstruct_itinerary

View Source

 1from collections import defaultdict
 2
 3
 4# @leet start
 5class Solution:
 6    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
 7        """
 8        This question asks us to find a path given a list of flights from one
 9        place to another.
10
11        We also want to find the lexically shortest path if there is more
12        than one path, so we first sort the tickets in reverse order before
13        placing them in our adjacency list, because we want to pop them.
14        We could sort in normal order and use a deque to pop from the beginning
15        as well.
16
17        Then, we define a DFS algorithm, which tries to fly through all of the
18        flights by doing a post order traversal, where we want to visit each neighbor
19        before we visit the current node.
20
21        So, for each flight we see, we take its remaining flights, and take the last
22        flight in its list of available flights, and DFS on that flight.
23        When there are no flights left, we append our flight to the result.
24        At the end, we're given a valid itinerary, just in reverse order.
25
26        For example, with an itinerary of ((MUC, LHR), (JFK, MUC), (SFO, SJC),
27        (LHR, SFO))
28
29        We would fly like so:
30
31        JFK ['MUC']
32        MUC ['LHR']
33        LHR ['SFO']
34        SFO ['SJC']
35        SJC []
36
37        And then at SJC, we would have no flights to go to, so we would
38        append ourselves to the output, and then go up the stack, to
39        SFO, LHR, MUC, JFK.
40
41        Which gives us:
42
43        ['SJC', 'SFO', 'LHR', 'MUC', 'JFK']
44
45        We can then just reverse this to get the correct answer.
46        """
47        tickets.sort(reverse=True)
48        adj = defaultdict(list)
49
50        for origin, dest in tickets:
51            adj[origin].append(dest)
52
53        def dfs(origin):
54            flights_out = adj[origin]
55            while flights_out:
56                dfs(flights_out.pop())
57            res.append(origin)
58
59        res = []
60        dfs("JFK")
61        return res[::-1]
62
63
64# @leet end
65
66
67def test():
68    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
 8        """
 9        This question asks us to find a path given a list of flights from one
10        place to another.
11
12        We also want to find the lexically shortest path if there is more
13        than one path, so we first sort the tickets in reverse order before
14        placing them in our adjacency list, because we want to pop them.
15        We could sort in normal order and use a deque to pop from the beginning
16        as well.
17
18        Then, we define a DFS algorithm, which tries to fly through all of the
19        flights by doing a post order traversal, where we want to visit each neighbor
20        before we visit the current node.
21
22        So, for each flight we see, we take its remaining flights, and take the last
23        flight in its list of available flights, and DFS on that flight.
24        When there are no flights left, we append our flight to the result.
25        At the end, we're given a valid itinerary, just in reverse order.
26
27        For example, with an itinerary of ((MUC, LHR), (JFK, MUC), (SFO, SJC),
28        (LHR, SFO))
29
30        We would fly like so:
31
32        JFK ['MUC']
33        MUC ['LHR']
34        LHR ['SFO']
35        SFO ['SJC']
36        SJC []
37
38        And then at SJC, we would have no flights to go to, so we would
39        append ourselves to the output, and then go up the stack, to
40        SFO, LHR, MUC, JFK.
41
42        Which gives us:
43
44        ['SJC', 'SFO', 'LHR', 'MUC', 'JFK']
45
46        We can then just reverse this to get the correct answer.
47        """
48        tickets.sort(reverse=True)
49        adj = defaultdict(list)
50
51        for origin, dest in tickets:
52            adj[origin].append(dest)
53
54        def dfs(origin):
55            flights_out = adj[origin]
56            while flights_out:
57                dfs(flights_out.pop())
58            res.append(origin)
59
60        res = []
61        dfs("JFK")
62        return res[::-1]

def findItinerary(self, tickets: list[list[str]]) -> list[str]: View Source

 7    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
 8        """
 9        This question asks us to find a path given a list of flights from one
10        place to another.
11
12        We also want to find the lexically shortest path if there is more
13        than one path, so we first sort the tickets in reverse order before
14        placing them in our adjacency list, because we want to pop them.
15        We could sort in normal order and use a deque to pop from the beginning
16        as well.
17
18        Then, we define a DFS algorithm, which tries to fly through all of the
19        flights by doing a post order traversal, where we want to visit each neighbor
20        before we visit the current node.
21
22        So, for each flight we see, we take its remaining flights, and take the last
23        flight in its list of available flights, and DFS on that flight.
24        When there are no flights left, we append our flight to the result.
25        At the end, we're given a valid itinerary, just in reverse order.
26
27        For example, with an itinerary of ((MUC, LHR), (JFK, MUC), (SFO, SJC),
28        (LHR, SFO))
29
30        We would fly like so:
31
32        JFK ['MUC']
33        MUC ['LHR']
34        LHR ['SFO']
35        SFO ['SJC']
36        SJC []
37
38        And then at SJC, we would have no flights to go to, so we would
39        append ourselves to the output, and then go up the stack, to
40        SFO, LHR, MUC, JFK.
41
42        Which gives us:
43
44        ['SJC', 'SFO', 'LHR', 'MUC', 'JFK']
45
46        We can then just reverse this to get the correct answer.
47        """
48        tickets.sort(reverse=True)
49        adj = defaultdict(list)
50
51        for origin, dest in tickets:
52            adj[origin].append(dest)
53
54        def dfs(origin):
55            flights_out = adj[origin]
56            while flights_out:
57                dfs(flights_out.pop())
58            res.append(origin)
59
60        res = []
61        dfs("JFK")
62        return res[::-1]

This question asks us to find a path given a list of flights from one place to another.

We also want to find the lexically shortest path if there is more than one path, so we first sort the tickets in reverse order before placing them in our adjacency list, because we want to pop them. We could sort in normal order and use a deque to pop from the beginning as well.

Then, we define a DFS algorithm, which tries to fly through all of the flights by doing a post order traversal, where we want to visit each neighbor before we visit the current node.

So, for each flight we see, we take its remaining flights, and take the last flight in its list of available flights, and DFS on that flight. When there are no flights left, we append our flight to the result. At the end, we're given a valid itinerary, just in reverse order.

For example, with an itinerary of ((MUC, LHR), (JFK, MUC), (SFO, SJC), (LHR, SFO))

We would fly like so:

JFK ['MUC'] MUC ['LHR'] LHR ['SFO'] SFO ['SJC'] SJC []

And then at SJC, we would have no flights to go to, so we would append ourselves to the output, and then go up the stack, to SFO, LHR, MUC, JFK.

Which gives us:

['SJC', 'SFO', 'LHR', 'MUC', 'JFK']

We can then just reverse this to get the correct answer.

def test(): View Source

68def test():
69    assert 2 + 2 == 4