399. Evaluate Division

Problem Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

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]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

• 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 consist of lower case English letters

Python Solution

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Build graph
        graph = defaultdict(dict)
        for (x, y), val in zip(equations, values):
            graph[x][y] = val
            graph[y][x] = 1.0 / val
        
        def dfs(start: str, end: str, visited: set) -> float:
            # If either node doesn't exist in graph
            if start not in graph or end not in graph:
                return -1.0
            
            # If start equals end
            if start == end:
                return 1.0
            
            # Mark as visited
            visited.add(start)
            
            # Try all neighbors
            for neighbor, value in graph[start].items():
                if neighbor not in visited:
                    result = dfs(neighbor, end, visited)
                    if result != -1.0:
                        return value * result
            
            return -1.0
        
        # Process queries
        return [dfs(start, end, set()) for start, end in queries]

Java Solution

class Solution {
    private Map> graph;
    
    public double[] calcEquation(List> equations, double[] values, List> queries) {
        // Build graph
        graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String x = equations.get(i).get(0);
            String y = equations.get(i).get(1);
            double val = values[i];
            
            graph.putIfAbsent(x, new HashMap<>());
            graph.putIfAbsent(y, new HashMap<>());
            graph.get(x).put(y, val);
            graph.get(y).put(x, 1.0 / val);
        }
        
        // Process queries
        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            result[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), new HashSet<>());
        }
        
        return result;
    }
    
    private double dfs(String start, String end, Set visited) {
        // If either node doesn't exist in graph
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            return -1.0;
        }
        
        // If start equals end
        if (start.equals(end)) {
            return 1.0;
        }
        
        // Mark as visited
        visited.add(start);
        
        // Try all neighbors
        for (Map.Entry neighbor : graph.get(start).entrySet()) {
            if (!visited.contains(neighbor.getKey())) {
                double result = dfs(neighbor.getKey(), end, visited);
                if (result != -1.0) {
                    return neighbor.getValue() * result;
                }
            }
        }
        
        return -1.0;
    }
}

C++ Solution

class Solution {
private:
    unordered_map> graph;
    
    double dfs(const string& start, const string& end, unordered_set& visited) {
        // If either node doesn't exist in graph
        if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
            return -1.0;
        }
        
        // If start equals end
        if (start == end) {
            return 1.0;
        }
        
        // Mark as visited
        visited.insert(start);
        
        // Try all neighbors
        for (const auto& [neighbor, value] : graph[start]) {
            if (visited.find(neighbor) == visited.end()) {
                double result = dfs(neighbor, end, visited);
                if (result != -1.0) {
                    return value * result;
                }
            }
        }
        
        return -1.0;
    }
    
public:
    vector calcEquation(vector>& equations, vector& values, vector>& queries) {
        // Build graph
        for (int i = 0; i < equations.size(); i++) {
            const string& x = equations[i][0];
            const string& y = equations[i][1];
            double val = values[i];
            
            graph[x][y] = val;
            graph[y][x] = 1.0 / val;
        }
        
        // Process queries
        vector result;
        for (const auto& query : queries) {
            unordered_set visited;
            result.push_back(dfs(query[0], query[1], visited));
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
var calcEquation = function(equations, values, queries) {
    // Build graph
    const graph = new Map();
    for (let i = 0; i < equations.length; i++) {
        const [x, y] = equations[i];
        const val = values[i];
        
        if (!graph.has(x)) graph.set(x, new Map());
        if (!graph.has(y)) graph.set(y, new Map());
        graph.get(x).set(y, val);
        graph.get(y).set(x, 1.0 / val);
    }
    
    const dfs = (start, end, visited) => {
        // If either node doesn't exist in graph
        if (!graph.has(start) || !graph.has(end)) {
            return -1.0;
        }
        
        // If start equals end
        if (start === end) {
            return 1.0;
        }
        
        // Mark as visited
        visited.add(start);
        
        // Try all neighbors
        for (const [neighbor, value] of graph.get(start)) {
            if (!visited.has(neighbor)) {
                const result = dfs(neighbor, end, visited);
                if (result !== -1.0) {
                    return value * result;
                }
            }
        }
        
        return -1.0;
    };
    
    // Process queries
    return queries.map(([start, end]) => dfs(start, end, new Set()));
};

C# Solution

public class Solution {
    private Dictionary> graph;
    
    public double[] CalcEquation(IList> equations, double[] values, IList> queries) {
        // Build graph
        graph = new Dictionary>();
        for (int i = 0; i < equations.Count; i++) {
            string x = equations[i][0];
            string y = equations[i][1];
            double val = values[i];
            
            if (!graph.ContainsKey(x)) graph[x] = new Dictionary();
            if (!graph.ContainsKey(y)) graph[y] = new Dictionary();
            graph[x][y] = val;
            graph[y][x] = 1.0 / val;
        }
        
        // Process queries
        double[] result = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            result[i] = DFS(queries[i][0], queries[i][1], new HashSet());
        }
        
        return result;
    }
    
    private double DFS(string start, string end, HashSet visited) {
        // If either node doesn't exist in graph
        if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) {
            return -1.0;
        }
        
        // If start equals end
        if (start == end) {
            return 1.0;
        }
        
        // Mark as visited
        visited.Add(start);
        
        // Try all neighbors
        foreach (var neighbor in graph[start]) {
            if (!visited.Contains(neighbor.Key)) {
                double result = DFS(neighbor.Key, end, visited);
                if (result != -1.0) {
                    return neighbor.Value * result;
                }
            }
        }
        
        return -1.0;
    }
}