Problem Statement

You are given an array of strings called equations. Each string in this array represents a relationship between two variables and follows one of two formats: "a==b" or "a!=b". Here, a and b are lowercase letters.

Return true if it is possible to assign values to these variables such that all the given relationships are satisfied. Otherwise, return false.

Examples

Example 1:

• Input: equations = ["a==b", "b==c", "a==c", "d == b"]
• Output: true
• Explanation: All variables can be assigned the same value, satisfying all equations.

Example 2:

• Input: equations = ["a==b", "b!=c", "c==a"]
• Output: false
• Explanation: If a == b and c == a, then b == c, which contradicts b != c.

Example 3:

• Input: equations = ["c==b", "b!=c"]
• Output: false
• Explanation: The equations c == b and b != c directly contradict each other.

Constraints:

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] is a lowercase letter.
• equations[i][1] is either '=' or '!'.
• equations[i][2] is '='.
• equations[i][3] is a lowercase letter.

Solution

To solve this problem, we can use the Union-Find data structure. The Union-Find structure helps manage the equivalence classes of variables, making it efficient to determine if two variables are in the same class or not. The overall approach is to first process all equality equations to group variables into sets. After that, we process all inequality equations to ensure no contradictions exist between the sets.

This approach is effective because it separates the problem into manageable parts. First, it handles the equality constraints, ensuring all connected components are identified. Then, it checks the inequality constraints, confirming that no two variables in the same set violate the constraints. The Union-Find structure is optimal for this, as it provides near-constant time operations for union and find, ensuring the algorithm runs efficiently even for large inputs.

Step-by-step Algorithm

1. Initialize the parent array:

   • Create an array parent of size 26 (for each lowercase letter).
   • Initialize each element of the array such that parent[i] = i.

2. Define the find function:

   • This function takes an integer x and returns the root of x.
   • Use path compression to make future queries faster: if parent[x] is not x, set parent[x] to the result of find(parent[x]).

3. Define the union function:

   • This function takes two integers x and y and unions their sets.
   • Find the roots of x and y using the find function.
   • If the roots are different, set the root of x to be the root of y.

4. Process equality equations:

   • Iterate through each equation in the input array.
   • For each equation of the form "a==b":
     • Convert a and b to their respective indices (using a - 'a' and b - 'a').
     • Union the indices of a and b.

5. Process inequality equations:

   • Iterate through each equation in the input array.
   • For each equation of the form "a!=b":
     • Convert a and b to their respective indices.
     • Use the find function to check if the indices of a and b have the same root.
     • If they do, return false (indicating a contradiction).

6. Return the result:

   • If no contradictions are found after processing all equations, return true.

Algorithm Walkthrough

Let's consider the input questions = ["a==b", "b==c", "a==c", "d==b"].

• Initialization:

  • parent = [0, 1, 2, ..., 25]

• Equation "a==b":

  • Indices: a -> 0, b -> 1
  • Union: find(0) -> 0, find(1) -> 1
  • After union: parent[0] = 1
  • Updated parent array: [1, 1, 2, 3, ..., 25]

• Equation "b==c":

  • Indices: b -> 1, c -> 2
  • Union: find(1) -> 1, find(2) -> 2
  • After union: parent[1] = 2
  • Updated parent array: [1, 2, 2, 3, ..., 25]

• Equation "a==c":

  • Indices: a -> 0, c -> 2
  • Union: find(0) -> 1 -> 2, find(2) -> 2
  • After union: no change needed
  • Updated parent array: [2, 2, 2, 3, ..., 25]

• Equation "d==b":

  • Indices: d -> 3, b -> 1
  • Union: find(3) -> 3, find(1) -> 2
  • After union: parent[3] = 2
  • Updated parent array: [2, 2, 2, 2, ..., 25]

• Final check:

  • No inequality equations to check.
  • Return true.

Code