Short C++ DFS iterative 44ms solution with explanation. No recursive calls, no backtracking.


  • 39
    F
    class Solution {
    public:
    	vector<string> findItinerary(vector<pair<string, string>> tickets) {
    		// Each node (airport) contains a set of outgoing edges (destination).
    		unordered_map<string, multiset<string>> graph;
    		// We are always appending the deepest node to the itinerary, 
    		// so will need to reverse the itinerary in the end.
    		vector<string> itinerary;
    		if (tickets.size() == 0){
    			return itinerary;
    		}
    		// Construct the node and assign outgoing edges
    		for (pair<string, string> eachTicket : tickets){
    			graph[eachTicket.first].insert(eachTicket.second);
    		}
    		stack<string> dfs;
    		dfs.push("JFK");
    		while (!dfs.empty()){
    			string topAirport = dfs.top();
    			if (graph[topAirport].empty()){
    				// If there is no more outgoing edges, append to itinerary
    				// Two cases: 
    				// 1. If it searchs the terminal end first, it will simply get
    				//    added to the itinerary first as it should, and the proper route
    				//    will still be traversed since its entry is still on the stack.
    				// 2. If it search the proper route first, the dead end route will also
    				//    get added to the itinerary first.
    				itinerary.push_back(topAirport);
    				dfs.pop();
    			}
    			else {
    				// Otherwise push the outgoing edge to the dfs stack and 
    				// remove it from the node.
    				dfs.push(*(graph[topAirport].begin()));
    				graph[topAirport].erase(graph[topAirport].begin());
    			}
    		}
    		// Reverse the itinerary.
    		reverse(itinerary.begin(), itinerary.end());
    		return itinerary;
    	}
    };

  • 8
    8

    Nice Solution, Java version here:

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            List<String> ret = new ArrayList<String>();
            Map<String, PriorityQueue<String>> map = new HashMap<>();
            for(String[] ticket : tickets) {
                if(!map.containsKey(ticket[0])) {
                    map.put(ticket[0], new PriorityQueue<String>());
                }
                map.get(ticket[0]).offer(ticket[1]);;
            }
            Stack<String> stack = new Stack<String>();
            stack.push("JFK");
            while(!stack.isEmpty()) {
                String next = stack.peek();
                if(map.containsKey(next) && !map.get(next).isEmpty()) {
                    stack.push(map.get(next).poll());
                } else {
                    ret.add(next);
                    stack.pop();
                }
            }
            Collections.reverse(ret);
            return ret;
        }
    }

  • 0
    S

    Isn't it backtracking?


  • 1
    B

    It's very likely topology sort, remove edge that has zero out-degree in every iteration.


  • 0
    R

    You don't need Collections.reverse(ret) by using LinkedList instead of ArrayList. That way you can add elements to the head of the list in constant time by using addFirst method. Also, just learned today - per Javadoc Stack is deprecated, and the Deque is recommended instead. You can you ArrayDeque here (though from readability point of view I think Stack is better).


  • 0
    H

    Really smart idea to break loops. Considering topological sort cannot handle non-DAG graph, this method seems a more generic solution to sort both DAG and non-DAG. Of course topological sort has extra pruning based on the presumption of DAG.


Log in to reply
 

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