평가 부문 | Leetcode 24일차

You are given equations in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating-point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

from collections import defaultdict
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        g = defaultdict(list)
        for i in range(len(equations)):
            eq = equations[i]
            val = values[i]
            s, d = eq
            g[s].append((d, val))
            g[d].append((s, 1/val))
        head = (equations[0][0], 1)
        # print(g)
        def dfs(root, path, s, d):
            nonlocal st
            st.add(root[0])
            path = path + [root]
            if s in st and d in st:
                return path
            res = None
            for child in g.get(root[0], []):
                if child[0] not in st:
                    res =  dfs(child, path, s, d)
                    if res is not None:
                        return res
        ans = []
        for s, d in queries:
            if s == d:
                if s in g:
                    ans.append(1)
                else:
                    ans.append(-1)
                continue
            st = set()
            path = dfs((s, 1), [], s, d)
            if path is None:
                st = set()
                path = dfs((d, 1), [], s, d)
            if path is None:
                ans.append(-1)
            else:
                flag = False
                res = 1
                id_p = [el[0] for el in path]
                s_i = id_p.index(s)
                e_i = id_p.index(d)
                if s_i <= e_i:
                    for i in range(s_i + 1, e_i + 1):
                        res*= path[i][1]
                    ans.append(res)
                else:
                    for i in range(s_i, e_i, -1):
                        res *= 1/path[i][1]
                    ans.append(res)
        return ans