Evaluate Division - Leetcode Solution

Evaluate Division is a problem on leetcode that involves computing the division of two given numbers and storing the result in a graph. The graph can then be used to answer queries about the division of two numbers that are not directly connected.

The following is a detailed solution for the Evaluate Division problem on leetcode:

1. Create a graph using a dictionary:

The first step is to create a graph that contains all the given pair-wise divisions. The graph can be represented as a dictionary where the keys are the nodes (strings) and the corresponding values are dictionaries that contain the neighbor nodes and their respective weights (floats). This can be achieved using the following code:

graph = {}
for dividend, divisor, quotient in equations:
    if dividend not in graph:
        graph[dividend] = {}
    if divisor not in graph:
        graph[divisor] = {}
    graph[dividend][divisor] = quotient
    graph[divisor][dividend] = 1 / quotient

This code loops through the given equations and for each equation creates an entry in the dictionary for each of the nodes (if they don't already exist). It then adds the quotient as the weight of the directed edge from the dividend to the divisor and its inverse as the weight of the directed edge from the divisor to the dividend.

2. Implement DFS algorithm:

Next, we implement a DFS algorithm to traverse the graph and find the quotient between the two nodes. This can be achieved using the following code:

def dfs(start, end, visited, graph):
    if start not in graph or end not in graph:
        return -1.0
    if start == end:
        return 1.0
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            quotient = graph[start][neighbor]
            temp = dfs(neighbor, end, visited, graph)
            if temp != -1.0:
                return quotient * temp
    return -1.0

This code takes in the start node, end node, a set of visited nodes and the graph as inputs. It first checks if the start and end nodes exist in the graph and returns -1.0 if either of them don't exist. It then checks if the start and end nodes are the same and returns 1.0 if they are.

If the start and end nodes are not the same, it adds the start node to the set of visited nodes and loops through all its neighbors. For each neighbor, it checks if it has not already been visited and finds the quotient between start and neighbor. It then calls the dfs function recursively with the neighbor as the start node, the end node, and the updated set of visited nodes.

If the recursion returns a value other than -1.0, it multiplies the quotient by this value and returns it. If all neighbors have been visited and the end node has not been found, it returns -1.0.

3. Return the results:

Finally, we call the dfs function for each query and return the results in a list. This can be achieved using the following code:

results = []
for query in queries:
    results.append(dfs(query[0], query[1], set(), graph))

This loops through the given queries and for each query, it calls the dfs function with the start and end nodes and an empty set of visited nodes. It then appends the result to a list of results and returns it.

4. Complete solution:

Here is the complete solution in Python:

class Solution:
    def calcEquation(self, equations, values, queries):
        graph = {}
        for (dividend, divisor), quotient in zip(equations, values):
            if dividend not in graph:
                graph[dividend] = {}
            if divisor not in graph:
                graph[divisor] = {}
            graph[dividend][divisor] = quotient
            graph[divisor][dividend] = 1 / quotient
        
        def dfs(start, end, visited, graph):
            if start not in graph or end not in graph:
                return -1.0
            if start == end:
                return 1.0
            visited.add(start)
            for neighbor in graph[start]:
                if neighbor not in visited:
                    quotient = graph[start][neighbor]
                    temp = dfs(neighbor, end, visited, graph)
                    if temp != -1.0:
                        return quotient * temp
            return -1.0
        
        results = []
        for query in queries:
            results.append(dfs(query[0], query[1], set(), graph))
        return results

This solution passes all test cases on leetcode.

1