Clean python code with Hashmap and DFS

  • 0

    First we construct our directed graph with hashmap, then we search x/y with DFS.

    class Solution(object):
        def search(self, x, y, record, visited):
            if x not in record:
                return -1.0
            if y in record[x]:
                return record[x][y]
            for k, v in record[x].items():
                if k not in visited:
                    v1 =, y, record, visited)
                    if v1 != -1:
                        return v * v1
            return -1.0
        def calcEquation(self, equations, values, query):
            record = collections.defaultdict(dict)
            for (x, y), v in zip(equations, values):
                record[x][y] = v
                record[y][x] = 1.0 / v
                record[x][x] = record[y][y] = 1.0
            return [, y, record, set()) for x, y in query]

Log in to reply

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