Satisfiability of equality equations

Array String Union-Find Graph Theory

51.6% acceptance

Feb 25, 2026

4009

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names. Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn equations_possible(equations: Vec<String>) -> bool {
    let mut parent: Vec<usize> = (0..26).collect();
    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x { parent[x] = find(parent, parent[x]); }
      parent[x]
    }
    for eq in &equations {
      let b = eq.as_bytes();
      if b[1] == b'=' {
        let (a, c) = ((b[0] - b'a') as usize, (b[3] - b'a') as usize);
        let (ra, rc) = (find(&mut parent, a), find(&mut parent, c));
        parent[ra] = rc;
      }
    }
    for eq in &equations {
      let b = eq.as_bytes();
      if b[1] == b'!' {
        let (a, c) = ((b[0] - b'a') as usize, (b[3] - b'a') as usize);
        if find(&mut parent, a) == find(&mut parent, c) { return false; }
      }
    }
    true
  }
}