Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

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. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3]It’s lowercase
  4. equations[i][1]either'=', either'! '
  5. equations[i][2] 是 '='

Train of thought

This topic is a typical query set questions, if you are not clear what is the query set can first look at my article: JS in the query set

  1. If the equation is true, we just need to check whether the ones that are not equal are satisfied, and if they are all equal, we return themtrueCan;
  2. First, through a round of traversal, all the associations of all equal values are established;
  3. Through another round of traversal, determine whether all elements that are not equal to the left and right sides of the equation are in the same relation.

implementation

/ * * *@param {string[]} equations
 * @return {boolean}* /
var equationsPossible = function(equations) {
    const n = equations.length;
    const uf = new UnionFind(26);

    // create a correlation between all equals
    for (let i = 0; i < n; i++) {
        let [ a, b, c, d ] = equations[i];
        if (b === "=") {
            let index1 = a.charCodeAt() - 'a'.charCodeAt();
            let index2 = d.charCodeAt() - 'a'.charCodeAt(); uf.merge(index1, index2); }}// Determine if there is an association between all unequal objects
    for (let i = 0; i < n; i++) {
        let [ a, b, c, d ] = equations[i];
        if (b === "!") {
            let index1 = a.charCodeAt() - 'a'.charCodeAt();
            let index2 = d.charCodeAt() - 'a'.charCodeAt();
            if (uf.find(index1) === uf.find(index2)) {
                return false; }}}return true;
};

class UnionFind {
  constructor(n) {
    // At first each element is associated with itself, and we use the same index to identify it
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the associator of an element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Establish an association
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

In the first round, filter out the elements that are not equal. In the second round, filter out the elements that are not equal. This step will not change the original array, or it will need to create extra space.

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.