Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出list tickets,(tickets[i][0], tickets[i][1])表示一张票的起点和终点,每个站点用三个字母的字符串表示,从“JFK”站开始,历经所有站点,输出经过的节点的次序,若有不止一条线路,输出字母序最小的解,DFS,注意string list的拼接方式(后面加‘,’)。写法参考 -> https://leetcode.com/problems/reconstruct-itinerary/solutions/78772/python-dfs-backtracking/?envType=daily-question&envId=2023-09-14


 1 #332
 2 #Runtime: 62 ms (Beats 38.57%)
 3 #Memory: 14.1 MB (Beats 53.57%)
 4 
 5 class Solution(object):
 6     def findItinerary(self, tickets):
 7         """
 8         :type tickets: List[List[str]]
 9         :rtype: List[str]
10         """
11         node = defaultdict(list)
12         for (x, y) in tickets:
13             node[x] += y,
14         self.ans = ["JFK"]
15         def DFS(st):
16             if len(self.ans) == len(tickets) + 1:
17                 return self.ans
18             tp_dst = sorted(node[st])
19             for dst in tp_dst:
20                 node[st].remove(dst)
21                 self.ans += dst,
22                 ok = DFS(dst)
23                 if ok:
24                     return ok
25                 self.ans.pop()
26                 node[st] += dst,
27         return DFS("JFK")

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理