What is wrong with my solution?


  • 0
    I

    for some reason it gives the answer as "JFK" for the input [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

    class Solution(object):
        def dfs(self, adjList, city, remTickets, itinerary):
            if remTickets == 0:
                return itinerary
                
            if city in adjList:
                for dest in adjList[city]:
                    adjList[city].remove(dest)
                    itinerary.append(dest)
                    
                    res = self.dfs(adjList, dest, remTickets - 1, itinerary)
                    if res:
                        return res
                        
                    itinerary.pop()
                    adjList[city].append(dest)
                
            return None
                
        
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            if not tickets:
                return []
                
            adjList = {}
            for ticket in tickets:
                if ticket[0] not in adjList:
                    adjList[ticket[0]] = [ticket[1]]
                else:
                    adjList[ticket[0]].append(ticket[1])
                    
            for ticket in tickets:
                adjList[ticket[0]].sort()
                    
            itinerary = ["JFK"]
            self.dfs(adjList,"JFK",len(tickets),itinerary)
            return itinerary

Log in to reply
 

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