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 form at least one valid itinerary.
Example 1:
Input:
[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output:["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:
-------------------------Input:
[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output:["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]
. But it is larger in lexical order.
Solution #1
很直接的graph traversal,要对edge做visited,而不是node
class Solution { public List<String> findItinerary(String[][] tickets) { Map<String, Node> graph = buildGraph(tickets); List<String> rt = new ArrayList<>(); rt.add("JFK"); dfs(graph.get("JFK"), rt, tickets.length); return rt; } private boolean dfs(Node node, List<String> rt, int count) { if (count == 0) { return true; } for (int i = 0; i < node.next.size(); i++) { Node n = node.next.get(i); rt.add(n.airport); if (!node.visited[i]) { node.visited[i] = true; if (dfs(n, rt, count - 1)) return true; node.visited[i] = false; } rt.remove(rt.size() - 1); } return false; } private Map<String, Node> buildGraph(String[][] tickets) { Map<String, Node> graph = new HashMap<>(); for (String[] t : tickets) { if (!graph.containsKey(t[0])) { graph.put(t[0], new Node(t[0])); } if (!graph.containsKey(t[1])) { graph.put(t[1], new Node(t[1])); } graph.get(t[0]).next.add(graph.get(t[1])); } for (Node n : graph.values()) { Collections.sort(n.next, (a,b) -> a.airport.compareTo(b.airport)); n.visited = new boolean[n.next.size()]; } return graph; } class Node{ public String airport; public List<Node> next; public boolean[] visited; public Node(String airport) { this.airport = airport; next = new ArrayList<>(); } } }
Solution #2 Eulerian Path Algorithm,题目已经说了路径一定存在
Eulerian Path的特点是一笔画,所有graph里面最多只有1个node有incoming degree - outgoing == 1, 只有一个node outgoing degree - incoming == 1. 所有要么是若干个环状,要么是一个单条路径 + 若干个环状路径。算法就是遇到死路就back tracking继续。(看下面youtube的视频)
ref: https://www.youtube.com/watch?v=8MpoO2zA2l4
Code ref: https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C++
class Solution { public List<String> findItinerary(String[][] tickets) { Map<String, PriorityQueue<String>> map = new HashMap<>(); for (String[] t : tickets) { if (!map.containsKey(t[0])) { map.put(t[0],new PriorityQueue<String>((a,b) -> a.compareTo(b))); } map.get(t[0]).add(t[1]); } List<String> rt = new ArrayList<>(); dfs(map,rt,"JFK"); Collections.reverse(rt); return rt; } private void dfs(Map<String, PriorityQueue<String>> map, List<String> rt, String ap) { while (map.containsKey(ap) && !map.get(ap).isEmpty()) { dfs(map,rt, map.get(ap).poll()); } rt.add(ap); } }
No comments:
Post a Comment