I tried using a hashset to keep track of which tickets I used, but it gives wrong answer, why?


  • 0
    I
    import collections
    class Solution(object):
        def dfs(self, adjList, city, remTickets, itinerary, usedTickets):
            if remTickets == 0:
                return itinerary
              
            if city in adjList:
                for dest in sorted(adjList[city]):
                    if city + dest not in usedTickets:
                        usedTickets.add(city + dest)
                        itinerary.append(dest)
                            
                        potentialItinerary = self.dfs(adjList, dest, remTickets - 1, itinerary, usedTickets)
                        if potentialItinerary:
                            return potentialItinerary
                                
                        usedTickets.remove(city + dest)
                        itinerary.pop()
            return None
                
        
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            if not tickets:
                return []
                
            adjList = collections.defaultdict(list)
            for ticket in tickets:
                adjList[ticket[0]].append(ticket[1])
                    
            usedTickets = set()
            itinerary = ["JFK"]
            self.dfs(adjList, "JFK", len(tickets), itinerary, usedTickets)
            return itinerary

Log in to reply
 

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