Evaluate Division

https://leetcode.com/contest/leetcode-weekly-contest-4/problems/evaluate-division/

已经遇到两次了，比较trick的地方是要构建一个nested dictionary

在遍历时把

d[a][b]
d[b][a]
都存进去，然后通过 a/b * b / k = a / k
这样b可以被抵消掉的关系通过a,b,k 把所有通过 a - b, b - k 推倒出a - k的关系都求出来
最后检查query是否满足条件即可

from collections import defaultdict
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        d = defaultdict(dict)
        for eq, val in zip(equations,values):
            a,b = eq
            d[a][a] =1 
            d[b][b] = 1
            d[a][b] = val
            d[b][a] = 1/val
        
        for k in d:
            for i in d[k]:
                for j in d[k]:
                    d[i][j] = d[i][k] * d[k][j]
                    d[j][i] = 1 / d[i][j]
        
        return [d[a][b] if a in d and b in d[a] else -1 for a,b in queries]