399.md

399. Evaluate Division

Solution 1 (time O(n^3), space O(n^2))

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]
        """
        from collections import defaultdict
        info = defaultdict(dict)
        for (val1, val2), val in zip(equations, values):
            info[val1][val1] = info[val2][val2] = 1
            info[val1][val2], info[val2][val1] = val, 1 / val
        for k, i, j in itertools.permutations(info, 3):
            if k in info[i] and j in info[k]:
                info[i][j] = info[i][k] * info[k][j]
        return [info[val1].get(val2, -1) for (val1, val2) in queries]