[LeetCode]#1436. Destination City

Environment: Python 3.7

Key technique: collections.defaultdict, Hash Table

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"

Analysis:

1. Create Hash Table for path
2. Search all string list in Hash Table
3. If string doesn’t have pair, return it.

Solution:

import collections
class Solution:
   def destCity(self, paths):
hashtable = collections.defaultdict(str)
    
     ls = []
    
     for a,b in paths:
        hashtable[a] = b
        ls += a,
        ls += b,
        
     for ans in ls:
        if hashtable[ans] == "":
            return ans

Submissions:

Reference:

https://leetcode.com/problems/destination-city/discuss/615132/Python-Easy-to-Understand-solution-(-Using-hashmap-)