python 35ms DFS


  • 0
    Z

    The idea is simple, build a adjacency list from the given input, then run DFS.

    I am using start/end(node) instead of divisor/dividend, so you could easily see the DFS structure. Please check the comments in the code for more details.

    class Solution(object):
        def calcEquation(self, equations, values, queries):
    
            def dfs(start, end, visited):
                visited.add(start)
                if not start in index_map:
                    return -1.
                if end in index_map[start]:
                    return index_map[start][end]
                # recursively check if there is a path from start to end
                for neighbour in index_map[start].keys():
                    if neighbour in visited:
                        continue
                    found = dfs(neighbour, end, visited)
                    # break if we have found the end node
                    if found != -1:
                        # found target node, recursively mutiply them
                        return index_map[start][neighbour] * found
                return -1.
                
            index_map = defaultdict(dict)
            for i in range(len(equations)):
                start, end = equations[i]
                # building adjancency list
                index_map[start].update({end: values[i]})
                index_map[end].update({start: 1. / values[i]})
            return [dfs(*q, visited=set()) for q in queries]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.