332. Reconstruct Itinerary

[mengyushi]

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:

        '''
        DFS + stack

        from.    to
        ["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]

                  dst.  src
        graph = {"MUC":["LHR"],"JFK":["MUC"],"SFO":["SJC"], "LHR":["SFO"]}
        stack = ["JFK"]
        route = []

        graph = {"MUC":["LHR"],"JFK":[],"SFO":["SJC"], "LHR":["SFO"]}
        stack = ["JFK", "MUC"]
        route = []

        graph = {"MUC":[],"JFK":[],"SFO":["SJC"], "LHR":["SFO"]}
        stack = ["JFK", "MUC","LHR"]
        route = []    

        graph = {"MUC":[],"JFK":[],"SFO":["SJC"], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO"]
        route = []         

        graph = {"MUC":[],"JFK":[],"SFO":[], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO","SJC"]
        route = []         

        graph = {"MUC":[],"JFK":[],"SFO":[], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO"]
        route = ["SJC"]

        graph = {"MUC":[],"JFK":[],"SFO":[], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO"]
        route = ["SFO","SJC"]  

        graph = {"MUC":[],"JFK":[],"SFO":[], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO"]
        route = ["SFO","SFO","SJC"] 

        ...

        graph = {"MUC":[],"JFK":[],"SFO":[], "LHR":[]}
        stack = ["JFK", "MUC","LHR","SFO"]
        route = ["JFK", "MUC", "LHR", "SFO", "SJC"]

        Time Complexity: O(N)
        Space Complexity: O(N)

        '''

        graph = collections.defaultdict(list)
        stack = ["JFK"]
        route = []

        for dst, src in sorted(tickets)[::-1]:  # Order will be reversed when insert to route. Here put Z first.
            graph[dst].append(src)
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            route.insert(0, stack.pop())
        return route

[mengyushi]

    [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

    graph = {JFK:[(NRT),(KUL)], NRT:[(JFK)]}

    stack = [JFK]
    route = []

    stack = [JFK,KUL]
    stack = [JFK]
    route = [KUL]

    stack = [JFK,NRT]
    stack = [JFK,NRT,(JFK)]
    route = [JFK,KUL]

    stack = [JFK,(NRT)]
    route = [NRT,JFK,KUL]

    stack = [JFK]
    route = [JFK,NRT,JFK,KUL]