Leetcode: 332. Reconstruct Itinerary

Can we formulate the problem using graphs? Find an Eulerian path in Directed Graph. Time and space complexity is \(O(m)\) where \(m\) is the number of edges in the graph.

from typing import List


class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        A = {u: [] for u in set(u for t in tickets for u in t)}
        for u, v in tickets:
            A[u].append(v)
        for u in A:
            A[u].sort(reverse=True)
        st = ["JFK"]
        ans = []
        while st:
            if not A[st[-1]]:
                ans.append(st.pop())
            else:
                st.append(A[st[-1]].pop())
        ans.reverse()
        return ans


assert Solution().findItinerary(
    [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
) == ["JFK", "MUC", "LHR", "SFO", "SJC"]
assert Solution().findItinerary(
    [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
) == ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]