#332

Reconstruct Itinerary

master · 1610 · lc hard +32 · verified · 44.3% accepted · 6,309 likes · top 27%

⚑ DFS / BFS: Connected Components & Reachability

Description

You are given a list of airline tickets where tickets[i] = [fromi, toi] represents one flight. All tickets belong to a traveler departing from "JFK", so the itinerary must begin with "JFK". Every ticket must be used exactly once.

If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single string.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 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.

Code

1

2

3

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]: