332. Reconstruct Itinerary - cocoder39/coco39_LC GitHub Wiki

332. Reconstruct Itinerary

regular backtrack solution

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        self.flightMap = defaultdict(list)

        # Build the graph
        for ticket in tickets:
            origin, dest = ticket[0], ticket[1]
            self.flightMap[origin].append(dest)

        # Sort each adjacency list to maintain lexicographical order
        self.visitBitmap = {}
        for origin, itinerary in self.flightMap.items():
            itinerary.sort()
            self.visitBitmap[origin] = [False] * len(itinerary)

        self.flights = len(tickets)
        self.result = []
        route = ['JFK']
        self.backtracking('JFK', route)

        return self.result

    def backtracking(self, origin, route):
        if len(route) == self.flights + 1:
            self.result = route
            return True

        for i, nextDest in enumerate(self.flightMap[origin]):
            if not self.visitBitmap[origin][i]:
                # Mark the visit before the next recursion
                self.visitBitmap[origin][i] = True
                if self.backtracking(nextDest, route + [nextDest]):
                    return True
                # Backtrack: unmark the visit
                self.visitBitmap[origin][i] = False

        return False

special algorithm

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        flights = collections.defaultdict(list)
        for ticket in tickets:
            flights[ticket[0]].append(ticket[1])
        
        for origin, itinerary in flights.items():
            itinerary.sort(reverse=True)
        
        stack = ['JFK']
        path = []
        while stack:
            cur = stack[-1]
            if flights[cur]:
                next_destination = flights[cur].pop()
                stack.append(next_destination)
            else:
                path.append(stack.pop())
        return path[::-1]

a good explanation : dfs starts from J, then it would traversal A, C, D, A. Now the path is J -> A -> C -> D -> A, and it cannot go further. That is to say, D -> A is not a good choice. Try D -> B. Then the path becomes J -> A -> C -> D -> B -> C -> J -> D. All tickets have been traversed.

example

Key point: dfs with using stack multiset is used because of lexical order and that there are more than one ticket starting from a certain port to another port.

|V| is the number of ports and |E| is the number of tickets. Then T_buildGraph = O(|E| + |V| * lg |V|), T_dfs = O(|E|), thus T = O(|E| + |V| * lg |V|). S = O(|V| + |E|).

vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, multiset<string>> map;
        for (auto ticket : tickets) 
            map[ticket.first].insert(ticket.second);
        
        vector<string> path;
        stack<string> dfs;
        dfs.push("JFK");
        while (! dfs.empty()) {
            string port = dfs.top();
            if (! map[port].empty()) {
                dfs.push(*(map[port].begin()));
                map[port].erase(map[port].begin());
            }
            else {
                path.push_back(port);
                dfs.pop();
            }
        }
        
        reverse(path.begin(), path.end());
        return path;
    }
⚠️ **GitHub.com Fallback** ⚠️