332. Reconstruct Itinerary

Q:

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 from JFK. Thus, the itinerary must begin with JFK.

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 may 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.

A:
***************Sol 1 ******graph--> topological sort ***************


****************Sol 2 **************Hash ***************
下面这个结果不对，你看看是哪里错了？

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> res = new LinkedList();
        Map<String, List<String> > map = new HashMap();
        for(int i =0;i<tickets.length; i++){
            String start = tickets[i][0];
            String end = tickets[i][1];
            if(map.containsKey(start)){
                List<String> list = map.get(start);
                int n = list.size();
                for(int j =0; j<= n;j++) // insert sort
                    if(j==n || list.get(j).compareTo(end)>0)
                        list.add(j,end);
            }else{
                List<String> list = new LinkedList();
                list.add(end);
                map.put(start,list);
            }
        }
        String start = "JFK";
        res.add(start);
        while( !map.isEmpty() ){
            List<String> list = map.get(start);
            String end = null;
            if(list.size() > 1){
                for(int i =0;i<list.size();i++){
                    if(isLoop(map,list.get(i),list.get(i) )){
                        end = list.remove(i);
                        break;
                    }
                }
            }else{
                end = list.get(0);
                map.remove(start);
            }
            res.add(end);
            start = end;
        }
        return res;
    }
    private boolean isLoop(Map<String,List<String>> map, String originalStart, String curStart ){
        if(map.get(curStart)==null)
            return false;
        for(String tmp : map.get(curStart)){
            if(tmp.equals(originalStart))
                return true;
            if( isLoop(map,originalStart, tmp) )
                return true;
        }
        return false;
    }
}

**************不能基于现在的状态去选择最好的，只能是dfs试错了***********最终代码如下***********




Mistakes:
1: 这里有一个情况没有考虑到：就是

         如果 路程有环的话，需要先找  可以转回来的，最低string **********

2：  但上面的也不对：
J --> AS
A-->JS
S-->A上面的这个就不能简单的用loop回来做选择。（因为 A-->S --A 是闭环的。但是J-->S就无法跑了。