Evaluate division

Array String Depth-First Search Breadth-First Search Union-Find Graph Theory Shortest Path

64.0% acceptance

Jan 12, 2026

10162

1093

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. Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn calc_equation(equations: Vec<Vec<String>>, values: Vec<f64>, queries: Vec<Vec<String>>) -> Vec<f64> {
    let mut graph: std::collections::HashMap<String, Vec<(String, f64)>> = std::collections::HashMap::new();
    
    for (i, eq) in equations.iter().enumerate() {
      let (a, b) = (&eq[0], &eq[1]);
      graph.entry(a.clone()).or_insert_with(Vec::new).push((b.clone(), values[i]));
      graph.entry(b.clone()).or_insert_with(Vec::new).push((a.clone(), 1.0 / values[i]));
    }
    
    queries.iter().map(|q| {
      let (start, end) = (&q[0], &q[1]);
      if !graph.contains_key(start) || !graph.contains_key(end) {
        return -1.0;
      }
      if start == end {
        return 1.0;
      }
      
      let mut visited = std::collections::HashSet::new();
      Self::dfs(&graph, start, end, &mut visited)
    }).collect()
  }
  
  fn dfs(graph: &std::collections::HashMap<String, Vec<(String, f64)>>, current: &str, target: &str, visited: &mut std::collections::HashSet<String>) -> f64 {
    if current == target {
      return 1.0;
    }
    
    visited.insert(current.to_string());
    
    if let Some(neighbors) = graph.get(current) {
      for (next, value) in neighbors {
        if !visited.contains(next) {
          let result = Self::dfs(graph, next, target, visited);
          if result != -1.0 {
            return result * value;
          }
        }
      }
    }
    
    -1.0
  }
}