NeetCode #597LC-399MediumGraphsNC 250
← Back to All Problems#597 · #399 · Evaluate Division(除法求值)
📌 Problem Statement & Constraints
You are given
equations where equations[i] = [Ai, Bi] and values[i] means Ai / Bi = values[i]. Given queries, return the answer to each query Cj / Dj, or -1.0 if it cannot be determined. Constraints: 1 <= equations.length <= 20, 1 <= queries.length <= 20, variables are strings.💡 Core Algorithmic Approaches
- Model the variables as nodes in a weighted graph: an edge
A -> Bhas weightA / B. - A query
C / Dis the product of edge weights along a path fromCtoD. - DFS from the source, multiplying weights as you descend, and stop when the target is found.
- Unknown variables or disconnected pairs yield -1.0.
💻 Benchmark Python3 Implementation
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
from collections import defaultdict
g = defaultdict(list)
for (a, b), v in zip(equations, values):
g[a].append((b, v)) # a / b = v
g[b].append((a, 1 / v)) # b / a = 1/v
def dfs(src: str, dst: str, visited: set) -> float:
if src not in g or dst not in g:
return -1.0 # unknown variable
if src == dst:
return 1.0
visited.add(src)
for nxt, w in g[src]:
if nxt in visited:
continue
if nxt == dst:
return w
sub = dfs(nxt, dst, visited)
if sub != -1.0:
return w * sub # multiply along the path
return -1.0
return [dfs(c, d, set()) for c, d in queries]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(Q * (V + E)): each query runs one DFS.
💾 Space Complexity
O(V + E) for the graph plus O(V) per DFS.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the reverse edge with the reciprocal weight: the graph must be traversable in both directions.
- Dividing instead of multiplying along the path:
A/C = (A/B) * (B/C). - Not checking whether the variables exist: an unknown variable must yield -1.0.
- Reusing the
visitedset across queries: each query needs a fresh set.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.