EvaluateDivision.py

# Question link - https://leetcode.com/problems/evaluate-division/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Build an adjancently list 
        adj = collections.defaultdict(list) #Map a -> values of [b , a / b]

        # To create the graph, we need 
        for i , eq in enumerate(equations):
            a , b = eq
            adj[a].append([b , values[i]])
            adj[b].append([a , 1 / values[i]])

        # Function for bfs
        def bfs(src , target):
            if src not in adj or target not in adj:
                return -1
            q , visit = deque() , set()
            # For src we need to map a -> b with weight value of multiplication
            q.append([src , 1])
            visit.add(src)
            # if q is not empty 
            while q:
                node , wei = q.popleft()

                if node == target:
                    return wei
                
                for nei , weight in adj[node]:
                    if nei not in visit: 
                        q.append([nei , wei * weight])
                        visit.add(nei)

            return -1
            
        # Final result 
        return [bfs(q[0],q[1]) for q in queries]