Reconstruct Itinerary - Teeeeeebag/LeetCode GitHub Wiki

public class Solution {
    private void dfs(String airport, ArrayList<String> crt, int num, ArrayList<String> res, HashMap<String, ArrayList<String>> nextDest, HashMap<String, HashSet<Integer>> visited){
        if (res.size()!=0){
            return;
        }
        if(num == crt.size()){
            res.addAll(crt);
            return;
        }
        ArrayList<String> nextAirports = nextDest.get(airport);
        if (nextAirports == null){
            return;
        }
        for (int i=0; i<nextAirports.size(); ++i){
            if (visited.get(airport).contains(i)){
                continue;
            }
            crt.add(nextAirports.get(i));
            visited.get(airport).add(i);
            dfs(nextAirports.get(i), crt, num, res, nextDest, visited);
            visited.get(airport).remove(i);
            crt.remove(crt.size()-1);
        }
    }
    public List<String> findItinerary(String[][] tickets) {
        ArrayList<String> res = new ArrayList<>();
        HashMap<String, ArrayList<String>> nextDest = new HashMap<>();
        HashMap<String, HashSet<Integer>> visited = new HashMap<>();
        for (String[] ticket : tickets){
            if(!visited.containsKey(ticket[0])){
                visited.put(ticket[0], new HashSet<Integer>());
            }
            if(!nextDest.containsKey(ticket[0])){
                nextDest.put(ticket[0], new ArrayList<>());
            }
            nextDest.get(ticket[0]).add(ticket[1]);
        }
        Iterator it = nextDest.entrySet().iterator();
        while (it.hasNext()){
            Map.Entry me = (Map.Entry) it.next();
            Collections.sort((ArrayList<String>) me.getValue(), new Comparator<String>(){
                public int compare(String s1, String s2){
                    for (int i=0; i<3; ++i){
                        if(s1.charAt(i) > s2.charAt(i)){
                            return 1;
                        } else if(s1.charAt(i) < s2.charAt(i)){
                            return -1;
                        }
                    }
                    return 0;
                }
            });
        }
        dfs("JFK", new ArrayList<String>(Arrays.asList("JFK")), tickets.length+1, res, nextDest, visited);
        return res;
    }
}