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

  • 0
    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)
                        potentialItinerary = self.dfs(adjList, dest, remTickets - 1, itinerary, usedTickets)
                        if potentialItinerary:
                            return potentialItinerary
                        usedTickets.remove(city + dest)
            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:
            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.