"""
key is to store tickets information in default dictionary in lexical order.
and what to do when ran into destination before going through all tickets.
if encounter destination, add to result list first.
then reverse the result in the end.
"""
iterative solution
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
targets=collections.defaultdict(list)
for a , b in sorted(tickets)[::-1]:
targets[a]+=[b]
#print targets
route =[]
stack=['JFK']
while stack:
while targets[stack[-1]]:
stack.append(targets[stack[-1]].pop())
route.append(stack.pop())
return route[::-1]
recursive solution
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
targets=collections.defaultdict(list)
for a , b in sorted(tickets)[::-1]:
targets[a]+=[b]
#print targets
route =[]
def visit(airport):
while targets[airport]:
visit(targets[airport].pop())
route.append(airport)
visit('JFK')
return route[::-1]
332. Reconstruct Itinerary
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 这题做了一天。。一天。。上午拿到之后感觉挺easy的，我想像NQueens那样先DFS找到所有的解。结果怎么也无法...
- 把每个机场视为一个节点，一张机票视为连接两个机场节点的有向边，这道题实际上是求一个有向图的一笔画问题，即从一个确定...
- Given a list of airline tickets represented by pairs of d...
