My code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    private HashMap<String, List<String>> adj = new HashMap<String, List<String>>();
    public List<String> findItinerary(String[][] tickets) {
        for (int i = 0; i < tickets.length; i++) {
            String from = tickets[i][0];
            String to = tickets[i][1];
            if (!adj.containsKey(from)) {
                adj.put(from, new ArrayList<String>());
            }
            insert(to, adj.get(from));
        }
        int total = tickets.length + 1;
        List<String> ret = new ArrayList<String>();
        ret.add("JFK");
        helper("JFK", ret, 1, total);
        
        return ret;
    }
    
    private boolean helper(String from, List<String> ret, int num, int total) {
        if (num >= total) {
            return true;
        }
        else if (!adj.containsKey(from) || adj.get(from).size() == 0) {
            return false;
        }
        
        for (int i = 0; i < adj.get(from).size(); i++) {
            String to = adj.get(from).get(i);
            ret.add(to);
            adj.get(from).remove(i);
            boolean flag = helper(to, ret, num + 1, total);
            if (flag) {
                return true;
            }
            else {
                ret.remove(ret.size() - 1);
                adj.get(from).add(i, to);
            }
        }
        
        return false;
    }
    
    private void insert(String s, List<String> list) {
        for (int i = 0; i < list.size(); i++) {
            if (s.compareTo(list.get(i)) <= 0) {
                list.add(i, s);
                return;
            }
        }
        
        list.add(s);
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String[][] tickets = new String[][]{{"EZE","AXA"},{"TIA","ANU"},{"ANU","JFK"},{"JFK","ANU"},{"ANU","EZE"},{"TIA","ANU"},{"AXA","TIA"},{"TIA","JFK"},{"ANU","TIA"},{"JFK","TIA"}};
        List<String> ret = test.findItinerary(tickets);
        System.out.println(ret.toString());
        
    }
}

這道題目做完真的花了九牛二虎之力。。
原因是題目意思理解錯了。我以為只要找到一條路徑字典順序最小就行了，不用用光所有機票。
然后就直接貪心。
后來發(fā)現(xiàn)是要用光所有機票，找出字典順序最小的那一鏈。
其實思路還是很明顯的，建 graph
然后DFS
需要注意的是。
1 。
什么時候停止dfs
我以前以為是，當這個城市沒有飛往其他任何地方的機票時，停止。其實是錯的。
因為條件是用光所有機票。所以當我們用的機票個數(shù)等于總機票個數(shù)時，就可以停止了。

2 。
遍歷相鄰結(jié)點，有序性的確保。
我一開始打算用TreeSet,然后他帶來的一個問題是，每當我用完一張機票，我需要把它從set里面刪掉，但是我遍歷的時候不能刪除，否則會有 concurrent exception
于是我采用簡單的。
for (int i = 0; i < size; i++) {...}
來遍歷，同時設置一個Hashset用來 存所有用過的機票，這樣我就不用從set里面刪除了。

String ticket = from + "->" + to;
if (set.contains(ticket)) {
  continue;
}
else {...}

然后發(fā)現(xiàn)了一個致命問題，
機票可能會有重復，即，
JFK -> AMI 的機票可能會有兩站，都得用了。
那么，我的set將不可能再被使用了。。。。

于是放棄了，看了答案，
reference:
https://discuss.leetcode.com/topic/36621/java-11ms-solution-hashmap-sorted-list

最關鍵的就是用，list，一開始構(gòu)建圖的時候，得確保鄰居結(jié)點在鏈表中的有序性。所以單獨寫了一個函數(shù)。

還有就是 total = tickets.length + 1;

這個得自己體會下。

Anyway, Good luck, Richardo! -- 09/11/2016