Closed congr closed 5 years ago
O(NLogN), where N is the number of tickets.
class Solution {
public List<String> findItinerary(String[][] tickets) {
map = new HashMap();
list = new ArrayList();
for (String[] t: tickets)
map.computeIfAbsent(t[0], k -> new PriorityQueue()).add(t[1]); // !!!
dfs("JFK");
return list;
}
Map<String, PriorityQueue<String>> map;
List<String> list;
void dfs (String here) {
while (map.containsKey(here) && !map.get(here).isEmpty())
dfs(map.get(here).remove());
list.add(0, here); // route
}
}
https://leetcode.com/problems/reconstruct-itinerary/