LC 990. Satisfiability of Equality Equations

发布时间：2020-12-14 04:25:15 所属栏目：大数据来源：网络整理

导读：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 necess

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.

Example 1:

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.

Example 2:

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

Example 3:

Input: ["a==b","b==c","a==c"]
Output: true

Example 4:

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

Example 5:

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

Note:

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0]?and?equations[i][3]?are lowercase letters
equations[i][1]?is either?‘=‘?or?‘!‘
equations[i][2]?is?‘=‘

Runtime:? 12 ms,faster than?100.00%?of?C++?online submissions for?Satisfiability of Equality Equations.

Memory Usage:? 7.1 MB,less than?100.00%?of?C++?online submissions for?Satisfiability of Equality Equations.

class Solution {

private:
  int arr[26];
public:

  void unionab(int a,int b) {
    arr[parent(a)] = arr[parent(b)];
  }
  int parent(int a) {
    if(arr[a] != a) return parent(arr[a]);
    return a;
  }
  bool uninit(int a) {
    return arr[a] == a ? true : false;
  }
  bool hassameroot(int a,int b) {
    return parent(a) == parent(b);
  }

  bool equationsPossible(vector<string>& equations) {
    for(int i=0; i<26; i++) arr[i] = i;
    for(int i=0; i<equations.size(); i++) {
      int a = ((int)equations[i][0] - (int)‘a‘);
      int b = ((int)equations[i][3] - (int)‘a‘);
      if ((int)equations[i][1] == (int)‘=‘) {
        if(!hassameroot(a,b)) unionab(a,b);
      }
    }
    for(int i=0; i<equations.size(); i++) {
      int a = ((int)equations[i][0] - (int)‘a‘);
      int b = ((int)equations[i][3] - (int)‘a‘);
      if((int)equations[i][1] == (int)‘!‘) {
        if(hassameroot(a,b)) return false;
      }
    }
    return true;
  }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!