Given a list of airline tickets represented by pairs of departure and arrival airports[from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs fromJFK. Thus, the itinerary must begin withJFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets=[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets=[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution: 用hashmap<depart, list<destination, visited>>建图，然后DFS找到路径。因为要返回字母顺序小的，所以要sort lists.

    boolean find = false;
    public List<String> findItinerary(String[][] tickets) {
        List<String> ans  = new ArrayList<>();
        if(tickets == null || tickets.length == 0 || tickets[0] == null || tickets[0].length == 0){
            return ans;
        }
        Map<String, List<Pair>> hashmap = new HashMap<>();
        for (String[] ticket : tickets) {
            List<Pair> destins = hashmap.get(ticket[0]);
            if (destins == null) {
                destins = new ArrayList<>();
                destins.add(new Pair(ticket[1], false));
                hashmap.put(ticket[0], destins);
            } else {
                destins.add(new Pair(ticket[1], false));
            }            
        }
        for (List<Pair> cur : hashmap.values()) {
            Collections.sort(cur, new Comparator<Pair>() {
                public int compare(Pair a, Pair b) {
                    return a.destin.compareTo(b.destin);
                }
            });
        }
        List<String> path = new ArrayList<>();
        path.add("JFK");
        helper(ans, path, hashmap, tickets.length + 1);
        return ans;
    }
    private void helper(List<String> ans, List<String> path, Map<String, List<Pair>> hashmap, int nums) {
        if (find) {
            return;
        }
        if (path.size() == nums) {
            //不能ans = new ArrayList<>(path);
            ans.addAll(path);
            find = true;
            return;
        }

        List<Pair> destins = hashmap.get(path.get(path.size() - 1));
        if (destins != null) {
            for (Pair cur : destins) {
                if (!cur.visited) {
                    path.add(cur.destin);
                    cur.visited = true;
                    helper(ans, path, hashmap, nums);
                    cur.visited = false;
                    path.remove(path.size() - 1);
                }
            }
        }
    }
    class Pair {
        String destin;
        boolean visited;
        public Pair(String s, boolean v) {
            destin = s;
            visited = v;
        }
    }