Java 14ms. DFS backtrack


  • 14
    A

    Calculate Euler path. For each point, try to DFS its out-going point. There is chance that a DFS won't get a result. So, we do backtrack. Out-going points should keep ascending order.

    public static List<String> findItinerary(String[][] tickets) {
        // construct graph
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
        ArrayList<String> al = null;
        for (String[] ticket : tickets) {
            al = graph.get(ticket[0]);
            if (al == null) {
                al = new ArrayList<String>();
                graph.put(ticket[0], al);
            }
            al.add(ticket[1]);
        }
        for (ArrayList<String> curr : graph.values()) {
            Collections.sort(curr);
        }
        ArrayList<String> ans = new ArrayList<>();
        itineraryHelper("JFK", ans, graph, tickets.length + 1);
        return ans;
    }
    
    // n is how many stops totally should contain
    public static boolean itineraryHelper(String curr, List<String> ans, HashMap<String, ArrayList<String>> graph, int n) {
        ans.add(curr);
        if (ans.size() >= n) {
            return true;
        }
        if (!graph.containsKey(curr) || graph.get(curr).isEmpty()) {
            return false;
        }
        ArrayList<String> arrivals = graph.get(curr);
        for (int i = 0; i < arrivals.size(); i++) { // iterate each arrival point
            String arrival = graph.get(curr).remove(i);
            if (itineraryHelper(arrival, ans, graph, n)) {
                return true;
            }
            ans.remove(ans.size() - 1); // backtrack
            arrivals.add(i, arrival);
        }
        return false;
    }

  • 0

    I notice that in each step, you delete the arrival from adjacent list and add back during backtrack. But in my implementation, I maintain a visited state, so for each adjacent nodes, check if visited or not. And it always gives me TLE. For those visited nodes, the loop will terminate early, it should not take much time.


  • 0
    P

    I got the same TLE problem as you...........


  • 0
    V

    It is interesting to note that you are not getting ConcurrentModificationException when you try to remove element from the arrivals list while iterating over it.. Does anyone know why?


  • 1
    A

    I tested below code. First loop throws Exception. Second doesn't. It seems naive for-loop doesn't check concurrency. Besides, in each loop in the code, the arrivales.size() keeps unchanged.

    ArrayList<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    for (String str : list) {   // will throw ConcurrentModificationException
        list.add("d");
    }
    for (int i = 0; i < list.size(); i++) {
        list.add("d");
    }

  • 0
    A

    you may attach your code. I can take a look.


  • 0

    Hi, below is my code, are there any bugs inside, it gives TLE.

    public class Solution {
        
        int locationCount;
        
        private boolean helper(String src, Map<String,List<String>> ticketMap, Set<String> visited, List<String> currentPath) {
            if(currentPath.size() == locationCount)
                return true;
            if(!ticketMap.containsKey(src))
                return false;
            List<String> destLst = ticketMap.get(src);
            for(String dest : destLst) {
               String travel = src + " " + dest;
                if(!visited.contains(travel)) {
                    visited.add(travel);
                    currentPath.add(dest);
                    if(helper(dest, ticketMap, visited, currentPath))
                        return true;
                    visited.remove(travel);
                    currentPath.remove(currentPath.size()-1);
                }
            }
            return false;
        }
        
        public List<String> findItinerary(String[][] tickets) {
            locationCount = tickets.length+1;
            Map<String,List<String>> ticketMap = new HashMap<String,List<String>>();
            for(String[] ticket : tickets) {
                if(ticketMap.containsKey(ticket[0]))
                    ticketMap.get(ticket[0]).add(ticket[1]);
                else {
                    List<String> l = new ArrayList<String>();
                    l.add(ticket[1]);
                    ticketMap.put(ticket[0], l);
                }
            }
            for(Map.Entry<String,List<String>> entry : ticketMap.entrySet())
                Collections.sort(entry.getValue());
            
            List<String> path = new ArrayList<String>();
            path.add("JFK");
            helper("JFK", ticketMap, new HashSet<String>(), path);
            return path;
        }
    }

  • 0
    A

    The code looks correct. I guess the hash code calculation takes a bit longer time Because the string length.


  • 0

    I also think so, and later it can takes many times to calculate the hashcode, if we shorten the neighbours, later we don't have to visit it again. Thanks for your help.


  • 0
    I

    Why are you removing the flight from your adjacency list before recursing to it?


  • 0
    J

    Though your code can pass the test , but if given [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"],["AAA","AAB"]], the result is different from the test answer. I just wonder the test is OK for this problem or not?


  • 0
    S

    you can use a wrapper class which has a field "used" or "visit"


  • 1
    6

    @IWantToPass because you don't want loop, you have chosen it so that you can't choose it again


  • 0
    Z

    @pinkfloyda Strange... Got almost the same solution with yours, but this solution failed in this case. (Not correct instead of TLE)

    [["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"],["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
    

    0_1492467499435_lc332_test.jpeg

    It will only return ["JFK"].

    I will come back later if I figure it out...


  • 0
    Z

    Big lesson to learn, Java's HashSet seems to behave differently than I expected. Have to use a Map<String, boolean[]> visited instead of Set<String> visited to mark all the visited edges.

    Here is the AC code.

    public class Solution {
        
    
        public List<String> findItinerary(String[][] tickets) {
            Map<String, List<String>> graph = new HashMap<>();
            // record the edges we have visited
            Map<String, boolean[]> visited = new HashMap<>();
            for (String[] t : tickets) {
                if (!graph.containsKey(t[0])) {
                    graph.put(t[0], new ArrayList<>());
                }
                graph.get(t[0]).add(t[1]);
            }
            for (String key : graph.keySet()) {
                Collections.sort(graph.get(key));
                visited.put(key, new boolean[graph.get(key).size()]);
            }
            
            int n = tickets.length + 1;
      
            List<String> path = new ArrayList<>();
            search("JFK", graph, n, path, visited);
            return path;
        }
        
        // backtrack
        private boolean search(String cur, Map<String, List<String>> graph, int n, List<String> path, Map<String, boolean[]> visited) {
            path.add(cur);
            // reach last level
            if (path.size() == n) {
                return true;
            }
            List<String> arrivals = graph.get(cur);
            if (arrivals == null) {
                path.remove(path.size() - 1);
                return false;
            };
            for (int i = 0; i < arrivals.size(); i++) {
                String arrival = arrivals.get(i);
                if (visited.get(cur)[i]) continue;
                visited.get(cur)[i] = true;
                if (search(arrival, graph, n, path, visited)) return true;
                visited.get(cur)[i] = false;
            }
            path.remove(path.size() - 1);
            return false;
            
        }
        
    }
    

Log in to reply
 

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