Posted on 2023-09-14 15:56
Uriel 閱讀(43)
評論(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")