給定一組機票
tickets，每張票[from, to]代表一段航程。所有機票都要用完，從"JFK"出發，回傳字典序最小的行程。保證至少存在一個合法行程。
Example:
Input: tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]] Output: [“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]
Intuition
TIP
這是尤拉路徑 (Eulerian Path) 問題 — 走遍所有邊恰好一次。用 Hierholzer 演算法後序插入。
- 每張機票是一條有向邊，要走遍所有邊恰好一次
- 使用有序集合（PriorityQueue 或排序後的列表）保證字典序最小
- Hierholzer 演算法：DFS 到死路時將節點加入結果（後序），最後反轉
Approaches
1. DFS + Backtracking — O(E^d) / O(V + E)
- Idea: 從 JFK 出發做 DFS，每次選字典序最小的下一站，若無法用完所有票就回溯
- Time:
O(E^d)（回溯最壞情況，d 為遞迴深度） - Space:
O(V + E)
class Solution {
fun findItinerary(tickets: List<List<String>>): List<String> {
val graph = HashMap<String, MutableList<String>>()
for ((from, to) in tickets) {
graph.getOrPut(from) { mutableListOf() }.add(to)
}
for (key in graph.keys) graph[key]!!.sort()
val result = mutableListOf("JFK")
val totalEdges = tickets.size
fun backtrack(): Boolean {
if (result.size == totalEdges + 1) return true
val cur = result.last()
val neighbors = graph[cur] ?: return false
for (i in neighbors.indices) {
val next = neighbors[i]
neighbors.removeAt(i)
result.add(next)
if (backtrack()) return true
result.removeAt(result.lastIndex)
neighbors.add(i, next)
}
return false
}
backtrack()
return result
}
}⭐ 2. Hierholzer's Algorithm (Eulerian path) — O(E log E) / O(V + E)
- Idea: DFS 走到死路時才加入結果（後序），使用 PriorityQueue 保證字典序，最後反轉
- Time:
O(E log E)（PriorityQueue 操作） - Space:
O(V + E)
class Solution {
fun findItinerary(tickets: List<List<String>>): List<String> {
val graph = HashMap<String, PriorityQueue<String>>()
for ((from, to) in tickets) {
graph.getOrPut(from) { PriorityQueue() }.add(to)
}
val result = LinkedList<String>()
fun dfs(airport: String) {
val destinations = graph[airport]
while (destinations != null && destinations.isNotEmpty()) {
dfs(destinations.poll())
}
result.addFirst(airport)
}
dfs("JFK")
return result
}
}🔑 Takeaways
- Pattern: 尤拉路徑 — Hierholzer 演算法，後序加入 + 反轉
- Key trick: 使用 PriorityQueue 自動排序保證字典序最小；
result.addFirst()相當於後序反轉