Участник:Alexander Denisenko/evaluate-division

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def dfs(graph, start, end, visited):
            if graph[start] and start == end:
                return 1.0
 
            visited.add(start)
            for neighbour, val in graph[start]:
                if neighbour in visited:
                    continue
 
                tmp = dfs(graph, neighbour, end, visited)
                if tmp > 0:
                    return tmp * val
 
            return -1.0
 
        graph = collections.defaultdict(set)
        for items, v in zip(equations, values):
            x, y = items
            graph[x].add((y, v))
            graph[y].add((x, 1.0 / v))
 
        res = []
        for q in queries:
            res.append(dfs(graph, q[0], q[1], set()))
 
        return res