990. Satisfiability of Equality Equations

T: O(equations.length)

S: O(26)

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        for (String equation : equations) {
            char c[] = equation.toCharArray();
            if (c[1] == '=') {
                uf.union(c[0] - 'a', c[3] - 'a');
            }
        }
        for (String equation : equations) {
            char c[] = equation.toCharArray();
            if (c[1] == '!') {
                if (uf.connected(c[0] - 'a', c[3] - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }
}
class UnionFind {
    int[] parent;
    UnionFind(int n) {
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public void union(int i, int j) {
        int x = find(i);
        int y = find(j);
        if (x != y) {
            parent[x] = y;
        }
    }
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public boolean connected(int i, int j) {
        int x = find(i);
        int y = find(j);
        return x == y;
    }
}