399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。 注意： 输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 注意： 未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例 1：

输入： equations = [["a","b"],"b","c"], values = 2.0,3.0, queries = [["a","c"],"b","a","a","e","a","a","x","x"] 输出：6.00000,0.50000,-1.00000,1.00000,-1.00000解释： 条件：a / b = 2.0,b / c = 3.0 问题：a / c = ?,b / a = ?,a / e = ?,a / a = ?,x / x = ? 结果：6.0, 0.5, -1.0, 1.0, -1.0 注意：x 是未定义的 => -1.0

示例 2：

输入： equations = [["a","b"],"b","c","bc","cd"], values = 1.5,2.5,5.0, queries = [["a","c"],"c","b","bc","cd","cd","bc"] 输出：3.75000,0.40000,5.00000,0.20000

示例 3：

输入： equations = [["a","b"]], values = 0.5, queries = [["a","b"],"b","a","a","c","x","y"] 输出：0.50000,2.00000,-1.00000,-1.00000

提示：

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj 由小写英文字母与数字组成

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

class Solution(object):
    def calcEquation(self, equations, values, queries):
        from collections import defaultdict
        graph = defaultdict(int)  # 构建图：key 是 (变量a, 变量b)，value 是 a / b 的结果
        set1 = set()
        for i in range(len(equations)):
            a, b = equations[i]
            graph[(a, b)] = values[i]  # a / b = 对应值
            graph[(b, a)] = 1 / values[i]  # b / a = 倒数
            set1.add(a)
            set1.add(b)
        
        arr = list(set1)
        # k 是中间节点：i -> k -> j，即 i/j = (i/k) * (k/j)
        for k in arr:
            for i in arr:
                for j in arr:
                    # 如果 i 能到 k，且 k 能到 j（值不为 0）
                    if graph[(i, k)] and graph[(k, j)]:
                        graph[(i, j)] = graph[(i, k)] * graph[(k, j)]
        
        res = []
        for x, y in queries:
            if graph[(x, y)]:
                res.append(graph[(x, y)])
            else:
                res.append(-1)
        return res
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """