题目链接
Satisfiability of Equality Equations - LeetCode
注意点
- 必须要初始化pre
解法
解法一：典型的并查集算法应用。先遍历所有等式，将等号两边的字母加入同一分类，每类中的字母都是相等的。然后遍历不等式，如果不等号两边的字母属于同一类则返回false。时间复杂度O(nm)
class Solution {
public:
map<char,char> pre;
char Find(char x)
{
char r = x;
while(pre[r] != r)
{
r = pre[r];
}
return r;
}
void Join(char x,char y)
{
char fx = Find(x);
char fy = Find(y);
if(fx != fy) pre[fx] = fy;
}
void Init()
{
char letter[26] ={'a','b','c','d','e','f','g','h','i',
'j','k','l','m','n','o','p','q','r',
's','t','u','v','w','x','y','z'};
for (auto l:letter)
{
pre[l] = l;
}
}
bool equationsPossible(vector<string>& equations) {
Init();
for(auto e:equations)
{
if(e[1] == '=') Join(e[0],e[3]);
}
for(auto e:equations)
{
if(e[1] == '!' && Find(e[0]) == Find(e[3]))
{
return false;
}
}
return true;
}
};