LeetCode 990. Satisfiability of Equality Equations

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

导读：原题链接在这里：https://leetcode.com/problems/satisfiability-of-equality-equations/ 题目： Given an array? equations ?of strings that represent relationships between variables,each string? equations[i] ?has length? 4 ?and takes one of two

原题链接在这里：https://leetcode.com/problems/satisfiability-of-equality-equations/

题目：

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?‘=‘

题解：

First,go through equations,union all with "==".

Then,go through equations again,if a!=b,but a and b are in the same union,then return false.

Time Complexity: O(nlogk). n = equations.length. k is number distinct character. Since k is single lower case,thus k <= 26.

Space: O(k).

AC Java:

 1 class Solution {
 2     HashMap<Character,Character> parent;
 3     
 4     public boolean equationsPossible(String[] equations) {
 5         if(equations == null || equations.length == 0){
 6             return true;
 7         }
 8         
 9         parent = new HashMap<>();
10         for(String s : equations){
11             if(s.substring(1,3).equals("==")){
12                 union(s.charAt(0),s.charAt(3));
13             }
14         }
15         
16         for(String s : equations){
17             if(s.substring(1,3).equals("!=") && find(s.charAt(0))==find(s.charAt(3))){
18                 return false;
19             }
20         }
21         
22         return true;
23     }
24     
25     private void union(char i,char j){
26         char p = find(i);
27         char q = find(j);
28         if(p != q){
29             parent.put(p,q);
30         }
31     }
32     
33     private char find(char c){
34         parent.putIfAbsent(c,c);
35         if(parent.get(c) != c){
36             char ancestor = find(parent.get(c));
37             parent.put(c,ancestor);
38         }
39         
40         return parent.get(c);
41     }
42 }

（编辑：李大同）

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