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.
1public class Solution {
2 public int Find(int[] parent, int x) {
3 if (parent[x] != x) {
4 parent[x] = Find(parent, parent[x]);
5 }
6 return parent[x];
7 }
8
9 public void Union(int[] parent, int x, int y) {
10 int rootX = Find(parent, x);
11 int rootY = Find(parent, y);
12 if (rootX != rootY) {
13 parent[rootY] = rootX;
14 }
}
public bool EquationsPossible(string[] equations) {
int[] parent = new int[26];
for (int i = 0; i < 26; i++) {
parent[i] = i;
}
foreach (var eq in equations) {
if (eq[1] == '=') {
int index1 = eq[0] - 'a';
int index2 = eq[3] - 'a';
Union(parent, index1, index2);
}
}
foreach (var eq in 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;
}
}This C# solution utilizes the union-find algorithm similarly to previous implementations. The solution handles each equation, leveraging union operations for '==' and raises failure scenarios using find methodology for '!=' equations if any connected variables conflict.
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.
#include <string>
#include <queue>
#include <cstring>
using namespace std;
class Solution {
public:
bool bfsCheck(vector<vector<int>>& graph, vector<bool>& visited, int start, int target) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 0; v < 26; ++v) {
if (graph[u][v] && !visited[v]) {
if (v == target) return true;
visited[v] = true;
q.push(v);
}
}
}
return false;
}
bool equationsPossible(vector<string>& equations) {
vector<vector<int>> graph(26, vector<int>(26, 0));
vector<bool> visited(26, false);
for (const auto& eq : equations) {
if (eq[1] == '=') {
int u = eq[0] - 'a';
int v = eq[3] - 'a';
graph[u][v] = graph[v][u] = 1;
}
}
for (const auto& eq : equations) {
if (eq[1] == '!') {
int u = eq[0] - 'a';
int v = eq[3] - 'a';
if (bfsCheck(graph, visited, u, v)) {
return false;
}
fill(visited.begin(), visited.end(), false);
}
}
return true;
}
};The BFS setup is similar to the C implementation, where each inequality check re-initializes visitation states. The solution systematically manages graph composition and per-equation checks to navigate potential conflicts using interlinked components.