Practice/Amazon/Leetcode 990. Satisfiability of Equality Equations

Leetcode 990. Satisfiability of Equality Equations

CodingMust

title: Validate Variable Equality System enableTestRunner: true testCases:

• name: "Simple valid system" input: | equations = ["a==b","b==c","c==a"] output: "true" explanation: "All three variables are equal to each other, forming one group. No contradictions exist." functionName: validateEquations args:

  • ["a==b","b==c","c==a"]

• name: "System with contradiction" input: | equations = ["a==b","b!=a"] output: "false" explanation: "The first equation states a equals b, but the second states they are not equal. This is a contradiction." functionName: validateEquations args:

  • ["a==b","b!=a"]

• name: "Complex valid system" input: | equations = ["a==b","b==c","a!=d","c!=e"] output: "true" explanation: "Variables a, b, and c form one equivalence group. Variables d and e are separate. Since d and e are not in the same group as the abc group, the inequalities are satisfied." functionName: validateEquations args:

  • ["a==b","b==c","a!=d","c!=e"]

• name: "Transitive contradiction" input: | equations = ["a==b","b==c","a!=c"] output: "false" explanation: "If a equals b and b equals c, then a must equal c by transitivity. The inequality a!=c creates a contradiction." functionName: validateEquations args:

  • ["a==b","b==c","a!=c"]

• name: "Single variable system" input: | equations = ["a==a"] output: "true" explanation: "A variable always equals itself. This is always satisfiable." functionName: validateEquations args:

  • ["a==a"]

• name: "Complex system with multiple groups" input: | equations = ["a==b","c==d","e==f","a!=c","c!=e","b!=d"] output: "true" explanation: "Three separate groups exist: {a,b}, {c,d}, and {e,f}. All inequalities are between different groups, so no contradictions occur." functionName: validateEquations args:

  • ["a==b","c==d","e==f","a!=c","c!=e","b!=d"] starterCode: python: | def validateEquations(equations: list[str]) -> bool: pass typescript: | function validateEquations(equations: string[]): boolean javascript: | function validateEquations(equations)

Problem

You are given an array of string equations representing relationships between variables. Each equation is one of two types:

• Equality: "x==y" means variable x must equal variable y
• Inequality: "x!=y" means variable x must not equal variable y

Each variable is represented by a single lowercase letter from 'a' to 'z'. Your task is to determine whether it's possible to assign values to all variables such that all equations are simultaneously satisfied.

Return true if a valid assignment exists, or false if the equations contain a logical contradiction.

Requirements

1. Process all equality equations to group variables that must be equal
2. After grouping, verify that no inequality equation connects two variables in the same group
3. Handle transitive relationships (if a==b and b==c, then a==c)
4. Return a boolean indicating whether the system is satisfiable

Constraints

• 1 ≤ equations.length ≤ 500
• equations[i].length == 4
• equations[i][0] and equations[i][3] are lowercase letters
• equations[i][1] is either '=' or '!'
• equations[i][2] is '='
• Each variable is a single lowercase letter ('a' to 'z')

Examples

Example 1:

Input: equations = ["a==b","b==c","c==a"] Output: true Explanation: All three variables belong to the same equivalence class, and no inequalities contradict this.

Example 2:

Input: equations = ["a==b","b!=a"] Output: false Explanation: The equality states a equals b, but the inequality states they must differ. This is impossible to satisfy.

Example 3:

Input: equations = ["a==b","b==c","a!=c"] Output: false Explanation: Through transitivity, a==c, which contradicts a!=c.

Example 4:

Input: equations = ["a==b","c==d","a!=c"] Output: true Explanation: Variables a and b form one group, c and d form another. The inequality between different groups is valid.