332. Reconstruct Itinerary

Hard

Description

給定一組機票 tickets，每張票 [from, to] 代表一段航程。所有機票都要用完，從 "JFK" 出發，回傳字典序最小的行程。保證至少存在一個合法行程。

Example:

Input: tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]] Output: [“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

Intuition#

這是尤拉路徑 (Eulerian Path) 問題 – 走遍所有邊恰好一次。用 Hierholzer 演算法後序插入。

每張機票是一條有向邊，要走遍所有邊恰好一次
使用有序集合（PriorityQueue 或排序後的列表）保證字典序最小
Hierholzer 演算法：DFS 到死路時將節點加入結果（後序），最後反轉

Approaches#

1: DFS + 回溯#

概念: 從 JFK 出發做 DFS，每次選字典序最小的下一站，若無法用完所有票就回溯
時間複雜度: O(E^d)（回溯最壞情況，d 為遞迴深度）
空間複雜度: 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 演算法（尤拉路徑）#

概念: DFS 走到死路時才加入結果（後序），使用 PriorityQueue 保證字典序，最後反轉
時間複雜度: O(E log E)（PriorityQueue 操作）
空間複雜度: 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 演算法，後序加入 + 反轉
關鍵技巧: 使用 PriorityQueue 自動排序保證字典序最小；result.addFirst() 相當於後序反轉