class Solution {
Map<String, PriorityQueue<String>> map;
public List<String> findItinerary(String[][] tickets) {
map = new HashMap<>();
for (String[] ticket: tickets) {
if (map.containsKey(ticket[0])) {
map.get(ticket[0]).add(ticket[1]);
} else {
PriorityQueue<String> minHeap = new PriorityQueue<>();
minHeap.add(ticket[1]);
map.put(ticket[0], minHeap);
}
}
List<String> result = new ArrayList<>();
result.add("JFK");
this.helper(result, "JFK", tickets.length);
return result;
}
private boolean helper(List<String> result, String cur, int count) {
if (count <= 0) {
return true;
}
if (!map.containsKey(cur)) {
return false;
}
PriorityQueue<String> oriHeap = (PriorityQueue)map.get(cur);
PriorityQueue<String> heap = new PriorityQueue<>(oriHeap);
while (!heap.isEmpty()) {
String loc = heap.poll();
oriHeap.remove(loc);
result.add(loc);
if (this.helper(result, loc, count - 1)) {
return true;
}
result.remove(result.size() - 1);
oriHeap.add(loc);
}
return false;
}
}
近期评论