LeetCode_990. Satisfiability of equality equations

Given an array of string equations representing relationships between variables, each equation [I] is of length 4 and takes one of two different forms: “A ==b” or” A! = b “. In this case, a and b are lowercase (not necessarily different) letters that represent single-letter variable names.

Return true only if an integer can be assigned to a variable name so that all given equations are satisfied, false otherwise.

Example 1:

Input: ["a==b","b!=a"] Output: false Explanation: If we specify a= 1 and b = 1, then the first equation can be satisfied, but not the second equation. There's no way to assign variables that satisfy both of these equations.Copy the code

Example 2:

Input: ["b==a","a==b"] Output: true Explanation: We can specify a= 1 and b= 1 to satisfy both equations.Copy the code

Example 3:

Input: ["a==b","b==c","a==c"] Output: trueCopy the code

Example 4:

Input: ["a==b","b!=c","c==a"] Output: falseCopy the code

Example 5:

Input: ["c==c","b==d","x!=z"] Output: trueCopy the code

Tip:

1 < = equations. Length < = 500 equations [I] length = = 4 equations [I] [0] and equations [I] [3] is lowercase equations [I] [1] is either ‘=’, Either ‘! ‘equations [I] [2] is’ =’

The problem can be solved by using the idea of searching set, which is a solution to the connectivity problem. The problem can simulate a, B, and C as points. A == B,b== C is equivalent to a connecting B, B connecting C, that is, the three are in a set. When b! =c, it is equivalent to finding and searching the parent nodes of the two points in the set. If they are the same, it means that a== B is in a set, and b! =c conflict, return false

code

/ * * *@param {string[]} equations
 * @return {boolean}* /
var equationsPossible = function (equations) {
    const set = new UnionSet(26)
    for (let i = 0; i < equations.length; i++) {
        if (equations[i][1] = ='! ') continue;
        const a = equations[i][0].charCodeAt() - 'a'.charCodeAt();
        const b = equations[i][3].charCodeAt() - 'a'.charCodeAt();
        set.merge(a, b)
    }

    for (let i = 0; i < equations.length; i++) {
        if (equations[i][1] = ='=') continue;
        const a = equations[i][0].charCodeAt() - 'a'.charCodeAt();
        const b = equations[i][3].charCodeAt() - 'a'.charCodeAt();
        if (set.find(a) === set.find(b)) return false
    }
    return true
};

var UnionSet = function (n) {
    this.fathers = new Array(n);
    this.size = new Array(n)
    for (let i = 0; i < n; i++) {
        this.fathers[i] = i
        this.size[i] = 1
    }

}

UnionSet.prototype.find = function (x) {
    if (this.fathers[x] === x) return x;
    return this.find(this.fathers[x])
}

UnionSet.prototype.merge = function (a, b) {
    const fa = this.find(a), fb = this.find(b);
    if (fa === fb) return;
    if (this.size[fa] < this.size[fb]) {
        this.fathers[fa] = fb
        this.size[fb] += this.size[fa]
    } else {
        this.fathers[fb] = fa
        this.size[fa] += this.size[fb]
    }
}

Copy the code