399. Evaluate Division (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        def dfs(path, val, target, j):
            if path[-1] == target:
                self.result[j] = val
            else:
                for i, (a, b) in enumerate(equations):
                    if path[-1] == a and b not in path:
                        dfs(path + [b], val * values[i], target, j)
        self.result = [-1] * len(queries)
        s = set(sum(equations, []))
        equations += [[b, a] for a, b in equations]
        values += [1/ x for x in values]
        for j, (a, b) in enumerate(queries):
            if a != b:
                dfs([a], 1, b, j)
            elif a in s:
                self.result[j] = 1
        return self.result