# Short Python solution DFS + Backtracking

• ``````class Solution(object):
def findItinerary(self, tickets):

def build_graph(tickets):
G = {}
for t in tickets:
S, E = t
G[S] = G.get(S, []) + [E]
for A in G:
G[A].sort(reverse=True)
G[A] = deque(G[A])
return G

def dfs(G, S):
trip.append(S)
if len(trip) == length:
return True
if S in G:
n, i = len(G[S]), 0
while i < n:
A = G[S].pop()
if dfs(G, A):
return True
G[S].appendleft(A)
i += 1
trip.pop()
return False

G = build_graph(tickets)
trip, length = [], len(tickets) + 1
dfs(G, "JFK")
return trip``````

• agave, your solution is absolutely genius. I just shorted in a bit and made it more 'idiomatic':

``````from collections import deque,defaultdict
class Solution(object):
def findItinerary(self, tickets):

def build_graph(tickets):
G = defaultdict(list)
for S, E in tickets:
G[S].append(E)
for A in G:
G[A].sort(reverse=True)
G[A] = deque(G[A])
return G

def dfs(G, S):
trip.append(S)
if len(trip) == length:
return True
if S in G:
queue=G[S]
for i in xrange(len(queue)):
A = queue.pop()
if dfs(G, A):
return True
queue.appendleft(A)
trip.pop()
return False

G = build_graph(tickets)
trip, length = [], len(tickets) + 1
dfs(G, "JFK")
return trip``````

• @yigalirani no genius, just plain DFS + backtracking, nothing out of the ordinary...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.