Very Straightforward DFS Solution with Detailed Explanations


  • 16
    Y

    The nice thing about DFS is it tries a path, and if that's wrong (i.e. path does not lead to solution), DFS goes one step back and tries another path. It continues to do so until we've found the correct path (which leads to the solution). You need to always bear this nice feature in mind when utilizing DFS to solve problems.

    In this problem, the path we are going to find is an itinerary which:

    1. uses all tickets to travel among airports
    2. preferably in ascending lexical order of airport code

    Keep in mind that requirement 1 must be satisfied before we consider 2. If we always choose the airport with the smallest lexical order, this would lead to a perfectly lexical-ordered itinerary, but pay attention that when doing so, there can be a "dead end" somewhere in the tickets such that we are not able visit all airports (or we can't use all our tickets), which is bad because it fails to satisfy requirement 1 of this problem. Thus we need to take a step back and try other possible airports, which might not give us a perfectly ordered solution, but will use all tickets and cover all airports.

    Thus it's natural to think about the "backtracking" feature of DFS. We start by building a graph and then sorting vertices in the adjacency list so that when we traverse the graph later, we can guarantee the lexical order of the itinerary can be as good as possible. When we have generated an itinerary, we check if we have used all our airline tickets. If not, we revert the change and try another ticket. We keep trying until we have used all our tickets.

    public class Solution {
        private HashMap<String, List<String>> adjList = new HashMap<>();
        private LinkedList<String> route = new LinkedList<>();
        private int numTickets = 0;
        private int numTicketsUsed = 0;
        
        public List<String> findItinerary(String[][] tickets) {
            if (tickets == null || tickets.length == 0) return route;
            // build graph
            numTickets = tickets.length;
            for (int i = 0; i < tickets.length; ++i) {
                if (!adjList.containsKey(tickets[i][0])) {
                    // create a new list
                    List<String> list = new ArrayList<>();
                    list.add(tickets[i][1]);
                    adjList.put(tickets[i][0], list);
                } else {
                    // add to existing list
                    adjList.get(tickets[i][0]).add(tickets[i][1]);
                }
            }
            // sort vertices in the adjacency list so they appear in lexical order
            for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
                Collections.sort(entry.getValue());
            }
            
            // start DFS
            route.add("JFK");
            dfsRoute("JFK");
            return route;
        }
        
        private void dfsRoute(String v) {
            // base case: vertex v is not in adjacency list
            // v is not a starting point in any itinerary, or we would have stored it
            // thus we have reached end point in our DFS
            if (!adjList.containsKey(v)) return;
            List<String> list = adjList.get(v);
            for (int i = 0; i < list.size(); ++i) {
                String neighbor = list.get(i);
                // remove ticket(route) from graph
                list.remove(i);
                route.add(neighbor);
                numTicketsUsed++;
                dfsRoute(neighbor);
                // we only return when we have used all tickets
                if (numTickets == numTicketsUsed) return;
                // otherwise we need to revert the changes and try other tickets
                list.add(i, neighbor);
                // This line took me a long time to debug
                // we must remove the last airport, since in an itinerary, the same airport can appear many times!!
                route.removeLast();
                numTicketsUsed--;
            }
        }
        
    }

  • 0
    P

    Clear idea!!!


  • 0
    C

    Beautiful code!


  • 0
    X

    Nice idea and clever code. I am wondering if anyone could translate this solution into C++, I failed to do so ;).


  • 0
    J

    Great idea! Below is my Java code with some improvements.

        // DFS method. We can return once we find the first valid solution.
        public List<String> findItinerary(String[][] tickets) {
            // Step 1: we build an adjacency matrix for this directed graph.
            Map<String, List<String>> myMap = new HashMap<>();
            for (String[] item: tickets) {
                String src = item[0];
                String dst = item[1];
                List<String> getList = myMap.get(src);
                if (getList == null) {
                    getList = new ArrayList<>();
                }
                getList.add(dst);
                myMap.put(src, getList);
            }
            // Sort the value for each key so that we prefer to use smaller String first.
            for (Map.Entry<String, List<String>> oneEntry: myMap.entrySet()) {
                Collections.sort(oneEntry.getValue());
            }
            // Step 2: Then we do DFS starting from JFK so as to get the first valid path.
            List<String> result = new ArrayList<>();
            result.add("JFK");
            int[] counter = new int[]{tickets.length};// we need to use up all of these tickets.
            if (DFS(myMap, "JFK", result, counter)) {
                return result;
            } else {
                return new ArrayList<>();
            }
        }
        private boolean DFS(Map<String, List<String>> myMap, String src, List<String> result, int[] counter) {
            // base case
            if (counter[0] == 0) {
                return true;
            }
            List<String> neighbors = myMap.get(src);
            if (neighbors == null || neighbors.size() == 0) {
                return false;
            }
            // at current layer, try its neighbors in the sorted order
            int curListSize = neighbors.size();
            for (int i = 0; i < curListSize; i ++) {
                String cur = neighbors.get(i);
                // put current neighbor into result
                result.add(cur);
                counter[0] --;
                // We also need to remove this ticket info from myMap so that it will not be used again.
                neighbors.remove(i);
                if (DFS(myMap, cur, result, counter)) {
                    return true;
                }
                // if cur path is not valid, we need to try another neighbor. 
                // Before that, we need to recover the previous state.
                result.remove(result.size() - 1);
                counter[0] ++;
                neighbors.add(i, cur);
            }
            return false;
        }
    
    

  • 0
    B

    Hi

    I have almost the same solution with you but I am not very clear about the time complexity. Is it exponential?

    Thanks


  • 0
    6

    i wonder whether LinkedList or ArrayList would be a better implementation of List interface in this situation.

    by the way why is it not correct to put "if (numTickets == numTicketsUsed) return; " before "dfsRoute(neighbor);" ?

    Thanks.


Log in to reply
 

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