Sponsored
Sponsored
This approach uses the Union-Find data structure to manage connectivity between variables. The core idea is to group variables that are known to be equal using '=='. After processing all such equations, we then check the '!=' equations to ensure that connected variables (i.e., variables that are in the same component) are not incorrectly marked as not equal.
Steps:
Time Complexity: O(n * α(n)) where n is the number of equations, and α is the inverse Ackermann function.
Space Complexity: O(1) as we are using a fixed-size array of 26 characters.
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 int find(vector<int>& parent, int x) {
8 if (parent[x] != x) {
9 parent[x] = find(parent, parent[x]);
10 }
11 return parent[x];
12 }
13
14 void unionSet(vector<int>& parent, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
bool equationsPossible(vector<string>& equations) {
vector<int> parent(26);
for (int i = 0; i < 26; i++) {
parent[i] = i;
}
for (const string& eq : equations) {
if (eq[1] == '=') {
int index1 = eq[0] - 'a';
int index2 = eq[3] - 'a';
unionSet(parent, index1, index2);
}
}
for (const string& eq : equations) {
if (eq[1] == '!') {
int index1 = eq[0] - 'a';
int index2 = eq[3] - 'a';
if (find(parent, index1) == find(parent, index2)) {
return false;
}
}
}
return true;
}
};The C++ solution follows the same logic as the C solution, but uses the vector data structure from the standard library for better type safety and easier management. The use of find and unionSet remains the same, managing connectivity for '==' equations and checking for invalid connectivity in '!=' equations.
Another method is to visualize the problem as a graph and determine if the '==' relations create valid partitions without violating '!=' conditions. This is managed using a BFS approach.
Steps:
Time Complexity: O(n) where n is the number of equations as each one is processed once during graph building and inequality checks.
Space Complexity: O(1) as it uses a fixed-size 26x26 adjacency matrix.
using System.Collections.Generic;
public class Solution {
private bool bfsCheck(List<int>[] graph, bool[] visited, int start, int target) {
var queue = new Queue<int>();
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (!visited[v]) {
if (v == target) return true;
visited[v] = true;
queue.Enqueue(v);
}
}
}
return false;
}
public bool EquationsPossible(string[] equations) {
var graph = new List<int>[26];
for (int i = 0; i < 26; i++) {
graph[i] = new List<int>();
}
bool[] visited = new bool[26];
foreach (var eq in equations) {
if (eq[1] == '=') {
int u = eq[0] - 'a';
int v = eq[3] - 'a';
graph[u].Add(v);
graph[v].Add(u);
}
}
foreach (var eq in equations) {
if (eq[1] == '!') {
int u = eq[0] - 'a';
int v = eq[3] - 'a';
if (bfsCheck(graph, visited, u, v)) {
return false;
}
Array.Fill(visited, false);
}
}
return true;
}
}The C# implementation writes adjacency information into lists per node for dynamic overlap handling. BFS traversals navigate components mapped by equational verifications, thereby conflicting '!=' suggestions are mitigated. Accessing internals by queue persists through boundary resets for exclusive sections.