399. Evaluate Division - cocoder39/coco39_LC GitHub Wiki

399. Evaluate Division

Option 1: dfs/bfs

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = collections.defaultdict(list)
        for i, equation in enumerate(equations):
            graph[equation[0]].append((equation[1], values[i]))
            graph[equation[1]].append((equation[0], 1/values[i]))
        
        def dfs(start, end, val, visited):
            if start == end:
                return val
            
            for next_node, v in graph[start]:
                if next_node not in visited:
                    visited.add(next_node)
                    res = dfs(next_node, end, val * v, visited)
                    if res != -1:
                        return res
            return -1
        
        res = []
        for start, end in queries:
            if start not in graph:
                res.append(-1)
            else:
                res.append(dfs(start, end, 1, set([start])))
        return res

Option 2: Unin find

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        root = {}
        
        def find(x):
            if x not in root:
                root[x] = (x, 1) # root[x] * ratio = x
                return root[x]
            
            root_of_group, ratio1 = root[x]
            if root_of_group != x:
                top_root, ratio2 = find(root_of_group)
                root[x] = (top_root, ratio1 * ratio2)
            return root[x]
        
        def union(x, y, ratio):
            root_of_x, ratio_x = find(x)
            root_of_y, ratio_y = find(y)
            
            if root_of_x != root_of_y:
                root[root_of_x] = (root_of_y, ratio_y*ratio/ratio_x)
            
        for i, equation in enumerate(equations):
            union(equation[0], equation[1], values[i])
        
        res = []
        for x, y in queries:
            if x not in root or y not in root:
                res.append(-1)
            else:
                root_of_x, ratio_x = find(x)
                root_of_y, ratio_y = find(y)
                if root_of_x != root_of_y:
                    res.append(-1)
                else:
                    res.append(ratio_x/ratio_y)
        return res