332. Reconstruct Itinerary

Loading...LeetCode

Backtracking 没法在过程中解决 lexical order的问题，找到所有解最后再挑选的话又会TLE，没想到其实是在前面生成hash map 的时候 sort 就行了...

思路其实是把无向连通图connectivity当作tree来做 DFS。

对当前 node 试着往下搜时，要把它的访问状态记录下来，以防形成环。如果没能在其子树中找到合格解，即需要返回，此时要恢复该 node 的访问状态（因为其他 node 的DFS可能再次搜索到它），再挑另一个 node 往下搜索。

Backtracking

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        travel = collections.defaultdict(list)
        query = collections.defaultdict(list)
        for f, t in sorted(tickets): 
            travel[f].append(t)
            query[f].append(False)
        n = len(tickets)+1
        return self.backtracking('JFK', ['JFK'], n, travel, query)
            
    
    def backtracking(self, f, itinerary, end, travel, query):
        if len(itinerary) == end:
            return itinerary
        
        for i, t in enumerate(travel[f]):
            if not query[f][i]:
                query[f][i] = True
                res = self.backtracking(t, itinerary+[t], end, travel, query)
                query[f][i] = False
                if res: return res