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:
- 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"].
- All airports are represented by three capital letters (IATA code).
- 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就无法跑了。