Posted on 2023-09-14 15:56
Uriel 阅读(12)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出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")