990. Satisfiability of Equality Equations(Leetcode每日一题-2020.06.08）

本文主要是介绍990. Satisfiability of Equality Equations(Leetcode每日一题-2020.06.08），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: “a==b” or “a!=b”. Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example1

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.

Example2

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

Example3

Input: [“a==b” , “b==c”,“a==c”]
Output: true

Example4

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

Example5

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

Solution

并查集


class UnionFind {
private:vector<int> parent;public:UnionFind() {parent.resize(26);iota(parent.begin(), parent.end(), 0);//从0开始，递增为每个迭代器赋值}int find(int index) {if (index == parent[index]) {return index;}parent[index] = find(parent[index]);return parent[index];}void unite(int index1, int index2) {parent[find(index1)] = find(index2);}
};class Solution {
public:bool equationsPossible(vector<string>& equations) {UnionFind uf;for(auto &equation: equations){if(equation[1] == '='){int index1 = equation[0] - 'a';int index2 = equation[3] - 'a';uf.unite(index1,index2);}}for(auto &equation: equations){if(equation[1] == '!'){int index1 = equation[0] - 'a';int index2 = equation[3] - 'a';if(uf.find(index1) == uf.find(index2))return false;}}return true;}
};