990. Satisfiability of Equality Equations

[Tcdian]

990. Satisfiability of Equality Equations

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 

Example 1

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.

Example 2

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3

Input: ["a==b","b==c","a==c"]
Output: true

Example 4

Input: ["a==b","b!=c","c==a"]
Output: false

Example 5

Input: ["c==c","b==d","x!=z"]
Output: true

Note

• 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 '='

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function(equations) {
    const unionFind = new UnionFind(26);
    for (let i = 0; i < equations.length; i++) {
        const variableFirst = equations[i].codePointAt(0) - 97;
        const variableSecond = equations[i].codePointAt(3) - 97;
        if (equations[i][1] === '=') {
            unionFind.union(variableFirst, variableSecond);
        }
    }
    for (let i = 0; i < equations.length; i++) {
        if (equations[i][1] === '!') {
            const variableFirst = equations[i].codePointAt(0) - 97;
            const variableSecond = equations[i].codePointAt(3) - 97;
            if (unionFind.isConnected(variableFirst, variableSecond)) {
                return false;
            }
        }
    }
    return true;
};

function UnionFind(size) {
    this._size = size;
    this._rank = new Array(size).fill(1);
    this._parent = Array.from(new Array(size), (val, index) => index);
}

UnionFind.prototype.union = function (p, q) {
    const pRoot = this.find(p);
    const qRoot = this.find(q);
    if(this._rank[pRoot] > this._rank[qRoot]) {
        this._parent[qRoot] = pRoot;
    } else if (this._rank[pRoot] < this._rank[qRoot]) {
        this._parent[pRoot] = qRoot;
    } else {
        this._parent[qRoot] = pRoot;
        this._rank[pRoot] += 1;
    }
}

UnionFind.prototype.isConnected = function (p, q) {
    const pRoot = this.find(p);
    const qRoot = this.find(q);
    return pRoot === qRoot;
}

UnionFind.prototype.find = function (p) {
    if (p >= this._size || p < 0) {
        throw new Error('out of bound');
    }
    while(this._parent[p] !== p) {
        p = this._parent[p];
    }
    return p;
}

• TypeScript Solution

function equationsPossible(equations: string[]): boolean {
    const unionFind = new UnionFind(26);
    for (let i = 0; i < equations.length; i++) {
        const variableFirst = equations[i].codePointAt(0) as number - 97;
        const variableSecond = equations[i].codePointAt(3) as number - 97;
        if (equations[i][1] === '=') {
            unionFind.union(variableFirst, variableSecond);
        }
    }
    for (let i = 0; i < equations.length; i++) {
        if (equations[i][1] === '!') {
            const variableFirst = equations[i].codePointAt(0) as number - 97;
            const variableSecond = equations[i].codePointAt(3) as number - 97;
            if (unionFind.isConnected(variableFirst, variableSecond)) {
                return false;
            }
        }
    }
    return true;
};

class UnionFind {
    private rank: number[];
    private parent: number[];
    constructor(private size: number = 0) {
        this.rank = new Array(size).fill(1);
        this.parent = Array.from(new Array(size), (val, index) => index);
    }
    union(p: number, q: number) {
        const pRoot = this.find(p);
        const qRoot = this.find(q);
        if (this.rank[pRoot] > this.rank[qRoot]) {
            this.parent[qRoot] = pRoot;
        } else if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot;
        } else {
            this.parent[qRoot] = pRoot;
            this.rank[pRoot] += 1;
        }
    }
    isConnected(p: number, q: number) {
        const pRoot = this.find(p);
        const qRoot = this.find(q);
        return pRoot === qRoot;
    }
    private find(p: number) {
        if (p >= this.size || p < 0) {
            throw new Error('out of bound');
        }
        while(this.parent[p] !== p) {
            p = this.parent[p];
        }
        return p;
    }
}