Kiểm tra tính hợp lệ của phương trình trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng arr làm đối số duy nhất. Mảng gồm các phương trình chuỗi của hai loại: 'X===Y' hoặc 'X!==Y' (X, Y là biến bất kỳ). Hàm kiểm tra xem có thể gán số cho các biến sao cho tất cả phương trình đều đúng không.

Ví dụ, nếu đầu vào là:

const arr = ['X===Y', 'Y!==Z', 'X===Z'];

Thì đầu ra nên là:

const output = false;

Giải thích đầu ra

Không thể chọn giá trị cho X, Y, Z thỏa mãn cả 3 phương trình cùng lúc.

Ví dụ minh họa

Mã thực hiện (Union-Find / Disjoint Set):

const arr = ['X===Y', 'Y!==Z', 'X===Z']; 
const validateEquations = (arr = []) => { 
  const map = {}; 
  const len = {}; 
  const inValids = []; 
  const find = (item) => { 
    while(map[item] && item !== map[item]){ 
      map[item] = map[map[item]]; 
      item = map[item]; 
    }; 
    return item; 
  }; 
  const add = (a, b) => { 
    const first = find(a); 
    const second = find(b); 
    if(first === second){ return; }; 
    if(len[first] < len[second]){ 
      map[first] = second; 
      len[second] += len[first]; 
    }else{ 
      map[second] = first; 
      len[first] += len[second]; 
    } 
  }; 
  arr.forEach((item) => { 
    const X = item[0]; 
    const Y = item[4]; 
    map[X] = map[X] || X; 
    map[Y] = map[Y] || Y; 
    len[X] = len[X] || 1; 
    len[Y] = len[Y] || 1; 
    if(item[1] === '!'){ 
      inValids.push([X, Y]); 
    }else{ 
      add(X, Y); 
    }; 
  }); 
  return inValids.every(([a, b]) => find(a) !== find(b)); 
}; 
console.log(validateEquations(arr));

Đầu ra

Kết quả trong console sẽ là:

false