Two Java solution (DFS+Stack && Backtrace+Recursion) very easy to understand


  • 7
    S

    I have used two method to solve this problem, the first one is a DFS using stack, the second one is backtrace. The backtrace one only uses 14ms, and the one with stack used 25ms. Personally, I prefer to use backtrace methods, because it is easy to understand, and it kind of has a "template" which you can apply to almost all backtrace problems.

    This is a DFS using stack:

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            List<String> result = new ArrayList();
            if(tickets == null || tickets.length == 0){
                return result;
            }
            Map<String, ArrayList<String>> graph = new HashMap();
        
            for(int i=0; i<tickets.length; i++){
                if(!graph.containsKey(tickets[i][0])){
                    ArrayList<String> adj = new ArrayList();
                    adj.add(tickets[i][1]);
                    graph.put(tickets[i][0], adj);
                }else{
                    ArrayList<String> newadj = graph.get(tickets[i][0]);
                    newadj.add(tickets[i][1]);
                    graph.put(tickets[i][0], newadj);
                }
            }
            for(ArrayList<String> a : graph.values()){
                Collections.sort(a);
            }
            
            Stack<String> stack = new Stack();
            stack.push("JFK");
            
            while(!stack.isEmpty()){
                
                while(graph.containsKey(stack.peek()) && !graph.get(stack.peek()).isEmpty()){
                    stack.push(graph.get(stack.peek()).remove(0));
                }
                result.add(0,stack.pop());
            }
            return result;
        }
    }
    

    This one is a backtrace method with recursion:

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            List<String> result = new ArrayList();
            if(tickets == null || tickets.length == 0){
                return result;
            }
            
            Map<String, ArrayList<String>> graph = new HashMap();
            for(int i=0; i<tickets.length; i++){
                if(!graph.containsKey(tickets[i][0])){
                    ArrayList<String> adj = new ArrayList();
                    adj.add(tickets[i][1]);
                    graph.put(tickets[i][0], adj);
                }else{
                    ArrayList<String> newadj = graph.get(tickets[i][0]);
                    newadj.add(tickets[i][1]);
                    graph.put(tickets[i][0], newadj);
                }
            }
            
            for(ArrayList<String> a : graph.values()){
                Collections.sort(a);
            }
            
            backtracing(result, "JFK", graph);
            
            return result;
        }
        
        public void backtracing(List<String> result, String current, Map<String, ArrayList<String>> graph){
            while(graph.containsKey(current) && !graph.get(current).isEmpty()){
                String s = graph.get(current).remove(0);
                backtracing(result, s, graph);
            }
            result.add(0,current);
        }
    }

  • 1
    A

    Thanks for sharing. I think the second solution is actually DFS. Backtracking normally reverts the changes after the recursive call, while here we remove the string and never put it back (we actually cannot in this case due to infinite loop, it's a graph removed means visited).
    And you might want to use linked lists instead since remove(0) and add(0) are quite expensive for ArrayLists.


Log in to reply
 

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