Backtracking and Euler Path/Euler Cycle
Solution 1: purely backtracking will get TLE
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
n = len(tickets) + 1
airports = [u for u, v in tickets] + [v for u, v in tickets]
airports = list(set(airports))
airport_idx = {airport:i for i, airport in enumerate(airports)}
m = len(airports)
itinerary_cnt = [[0]*m for _ in range(m)]
for u, v in tickets:
i, j = airport_idx[u], airport_idx[v]
graph[i].append(j)
itinerary_cnt[i][j] += 1
ret = None
def backtrack(i, curr, visited):
nonlocal ret
if len(curr) == n:
this_ret = [airports[i] for i in curr]
if ret is None:
ret = this_ret
else:
this_ret
ret = min(ret, this_ret, key = lambda x: "".join(x))
return
for j in graph[i]:
if visited[i][j] == itinerary_cnt[i][j]:
continue
visited[i][j] += 1
curr.append(j)
backtrack(j, curr, visited)
curr.pop()
visited[i][j] -= 1
curr = [airport_idx["JFK"]]
visited = [[0]*m for _ in range(m)]
backtrack(airport_idx["JFK"], curr, visited)
return ret
It is checking all the path since we need to find the min result. This makes the problem has a high complexity. However, at each step, we can play a trick to pick up the smallest next stop, then we can directly get the minimum ret. The complexity will be greatly reduced.
As purely use the smallet value will make we can not recover the whole iterators, so we still need use backtracking but with a specified order, then the first time found must be the smallest one.
[[“JFK”,”KUL”],[“JFK”,”NRT”],[“NRT”,”JFK”]]
Wrong solution 2: purely find only one path may get stuck due to no next stop to choose.
This solution will get wrong answer on above case
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
n = len(tickets) + 1
for u, v in tickets:
graph[u].append(v)
for key in graph.keys():
graph[key].sort(reverse=True)
def dfs(airport):
if len(ret) == n:
return
next_airport = graph[airport].pop()
ret.append(next_airport)
dfs(next_airport)
ret = ["JFK"]
dfs("JFK")
return retSolution 3: Improved version of solution 1: With improvement, still got TLE, but this time more cases can be passed
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph_ = collections.defaultdict(list)
n = len(tickets) + 1
airports = [u for u, v in tickets] + [v for u, v in tickets]
airports = list(set(airports))
airport_idx = {airport:i for i, airport in enumerate(airports)}
m = len(airports)
itinerary_cnt = [[0]*m for _ in range(m)]
for u, v in tickets:
i, j = airport_idx[u], airport_idx[v]
graph_[u].append(v)
itinerary_cnt[i][j] += 1
for key in graph_:
graph_[key].sort()
graph = {airport_idx[k]: [airport_idx[v_] for v_ in v] for k, v in graph_.items()}
ret = None
def backtrack(i, curr, visited):
nonlocal ret
if len(curr) == n:
ret = [airports[i] for i in curr]
return
if i not in graph:
return
for j in graph[i]:
if visited[i][j] == itinerary_cnt[i][j]:
continue
visited[i][j] += 1
curr.append(j)
backtrack(j, curr, visited)
if ret is not None:
return
curr.pop()
visited[i][j] -= 1
curr = [airport_idx["JFK"]]
visited = [[0]*m for _ in range(m)]
backtrack(airport_idx["JFK"], curr, visited)
return ret
Solution 4: Euler Cycle
Actually, this is a well know Euler Cycle problem. Euler cycle is a special case of Euler Path.
Euler Path is original from the Seven Bridges of Königsberg [1].
I will skip the explanation for this part, can search on the internet to find more.
Here is a solution based on solution 1:
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
relation_cnt = collections.defaultdict(lambda : collections.defaultdict(int))
visited = collections.defaultdict(lambda : collections.defaultdict(int))
for u, v in tickets:
relation_cnt[u][v] += 1
graph[u].append(v)
for k in graph.keys():
# to ensure the result has the smallest lexical order
graph[k].sort()
ret = []
def dfs(u):
for v in graph[u]:
if visited[u][v] == relation_cnt[u][v]:
continue
visited[u][v] += 1
dfs(v)
ret.append(v)
dfs("JFK")
ret.append("JFK")
return ret[::-1]If you understand the Euler Cycle problem, the coding is simple. How to understand the Euler Cycle problem take time. I am understanding it based on a Chinese video. If you have good English source, can post in comments.
The above code actually is not the optimized one, the time complexity can be O(E²) as we did not delete the used E and each time, we are checking whether the edge is used or not. We can use another way to remove the used edge on the fly. By this code, the complexity can be O(E). Code is here:
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
for u, v in tickets:
graph[u].append(v)
for k in graph.keys():
# to ensure the result has the smallest lexical order
graph[k].sort(reverse=True)
ret = []
def dfs(u):
while graph[u]:
v = graph[u].pop()
dfs(v)
ret.append(v)
dfs("JFK")
ret.append("JFK")
return ret[::-1]
