Skip to content

Latest commit

 

History

History
147 lines (85 loc) · 4.8 KB

0332._Reconstruct_Itinerary.md

File metadata and controls

147 lines (85 loc) · 4.8 KB

332. Reconstruct Itinerary

难度: Medium

刷题内容

原题连接

内容描述

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.

解题方案

思路 1 - 时间复杂度: O(ElgE)- 空间复杂度: O(E)******

参考

  1. 智慧巅峰
  2. Hierholzer’s Algorithm for directed graph
the idea is to keep following unused edges and removing them until we get stuck. 
Once we get stuck, we back-track to the nearest vertex in our current path that has unused edges, 
and we repeat the process until all the edges have been used. We can use another container to maintain the final path.
  • 我们从'JFK'出发，一直按照lexical order往下走，比如从'JFK'可以去'SFO'和'ATL‘，那么我们优先去'ATL'
  • 边走边消除ticket，也就是说我们从'JFK'出发去了'ATL'，那么ticket ["JFK","ATL"]就没了
  • 然后走到某一个位置的时候我们发现往下走不下去了，我们就将当前卡住的位置放到最终结果route中去，然后我们倒退一步看看除了这条路还有没有别的路走， 继续这个过程，直到我们回到'JFK'，且没有路走了，我们就将route逆序返回，即是结果，因为route的第一个点其实是我们最后到的点
input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

lookup:  [('SFO', ['ATL']), ('JFK', ['SFO', 'ATL']), ('ATL', ['SFO', 'JFK'])]
cur path:  ['JFK']  # 从'JFK'出发
cur path:  ['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']  # 走到'SFO'没地方走了
cur route:  ['SFO']  # 说明'SFO'是我们最后到达的地方

cur path:  ['JFK', 'ATL', 'JFK', 'SFO', 'ATL'] # 退一步回到'ATL'
cur path:  ['JFK', 'ATL', 'JFK', 'SFO', 'ATL'] # 发现'ATL'除了刚才的'SFO'也没地方可走了
cur route:  ['SFO', 'ATL'] # 说明此时'ATL'是我们最后到达的地方

cur path:  ['JFK', 'ATL', 'JFK', 'SFO'] # 退一步回到'SFO'
cur path:  ['JFK', 'ATL', 'JFK', 'SFO'] # 发现'SFO'没地方可走了
cur route:  ['SFO', 'ATL', 'SFO'] # 说明此时'SFO'是我们最后到达的地方

cur path:  ['JFK', 'ATL', 'JFK'] # 退一步回到'JFK'
cur path:  ['JFK', 'ATL', 'JFK'] # 发现'JFK'没地方可走了
cur route:  ['SFO', 'ATL', 'SFO', 'JFK'] # 说明此时'JFK'是我们最后到达的地方

cur path:  ['JFK', 'ATL'] # 退一步回到'ATL'
cur path:  ['JFK', 'ATL'] # 发现'ATL'没地方可走了
cur route:  ['SFO', 'ATL', 'SFO', 'JFK', 'ATL'] # 说明此时'ATL'是我们最后到达的地方

cur path:  ['JFK'] # 退一步回到'JFK'
cur path:  ['JFK'] # 发现'JFK'没地方可走了
cur route:  ['SFO', 'ATL', 'SFO', 'JFK', 'ATL', 'JFK'] # 说明此时'JFK'是我们最后到达的地方

此时cur path空了，说明我们完全没地方可去了，我们就直接返回route的逆序就可以了
  • time complexity if O(ELogE) where E is number of edges. Because we offer each edge into queue once and then poll it out once.
  • Space complexity is O(E).

beats 32.44%

class Solution:
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        lookup = collections.defaultdict(list)
        for start, end in sorted(tickets)[::-1]:
            lookup[start].append(end)
        # print('tickets: ', lookup.items())
        route, stack = [], ['JFK']
        while stack:
            # print('cur path: ', stack)
            while lookup[stack[-1]]:
                stack.append(lookup[stack[-1]].pop())
            # print('cur path: ', stack)
            route.append(stack.pop())
            # print('cur route: ', route)
            # print()
        return route[::-1]