[LeetCode] 332. Reconstruct Itinerary

 Problem : https://leetcode.com/problems/reconstruct-itinerary/

Consider each city is a vertex in a directed graph, then every ticket is an edge between 2 vertices.

Use one hash table to track all available tickets. ( Notice : There could be duplicated tickets between 2 cities )

Then use DFS to find the possible path between city "JFK" to the ending city.

DFS ends when number of city = total number of tickets  + 1

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        allTickets = defaultdict(int)
        
        for src, dst in tickets:
            graph[src].append(dst)
            allTickets[(src,dst)] += 1
        
        for src in graph.keys():
            graph[src].sort()
        
        
        def dfs(src, path):
            if len(path) == len(tickets) + 1:
                return path
            
            for dst in graph[src]:
                if allTickets[(src,dst)] > 0:
                    allTickets[(src,dst)] -= 1
                    
                    tmp = dfs(dst, path + [dst])
                    if tmp:
                        return tmp
                    
                    allTickets[(src,dst)] += 1
                    
            return None
        
    
        return dfs("JFK", ["JFK"])