You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.
Example 1:
Input: equations = ["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.
Example 2:
Input: equations = ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
Constraints:
1 <= equations.length <= 500equations[i].length == 4equations[i][0] is a lowercase letter.equations[i][1] is either '=' or '!'.equations[i][2] is '='.equations[i][3] is a lowercase letter.class Solution {
public:
void merge(int a, int b, vector<int>& dp){
for(int i=0; i<26; i++)
if(dp[i]==b)
dp[i]=a;
}
bool equationsPossible(vector<string>& equations) {
vector<int> dp(26, 0);
vector<string> notEqns;
int k=1;
for(auto eqn: equations){
if(eqn[1]=='!'){
notEqns.push_back(eqn);
continue;
}
int a = eqn[0]-'a', b = eqn[3]-'a';
if(dp[a]&&dp[b])
merge(dp[a],dp[b],dp);
else if(dp[a]||dp[b])
dp[a]=dp[b]=max(dp[a],dp[b]);
else dp[a]=dp[b]=k++;
}
for(auto eqn: notEqns)
if(eqn[0]==eqn[3] || (dp[eqn[0]-'a']==dp[eqn[3]-'a'] && dp[eqn[0]-'a']!=0))
return false;
return true;
}
};