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