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:
                    visited.add(k)
    
                    v1 = self.search(k, y, record, visited)
                    if v1 != -1:
                        return v * v1
    
                    visited.discard(k)
    
            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 [self.search(x, 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.