【leetcode】990. Satisfiability of Equality Equations

小鱼儿 2022-01-07 11:25 179阅读 0赞

**题目如下：**

> 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.  `1 <= equations.length <= 500`
> 2.  `equations[i].length == 4`
> 3.  `equations[i][0]` and `equations[i][3]` are lowercase letters
> 4.  `equations[i][1]` is either `'='` or `'!'`
> 5.  `equations[i][2]` is `'='`

**解题思路：**我的方法是用并查集，先把所有等式中的字母合并组成并查集，接下来再判断不等式中的字母是否属于同一祖先。

**代码如下：**

class Solution(object):
        def equationsPossible(self, equations):
            """
            :type equations: List[str]
            :rtype: bool
            """
            def find(v):
                if parent[v] == v:
                    return v
                return find(parent[v])
    
            def union(v1,v2):
                p1 = find(v1)
                p2 = find(v2)
                if p1 < p2:
                    parent[p2] = p1
                else:
                    parent[p1] = p2
            parent = [i for i in range(26)]
    
            uneuqal = []
            while len(equations) > 0:
                item = equations.pop(0)
                if item[1] == '!':
                    uneuqal.append(item)
                else:
                    union(ord(item[0]) - ord('a'),ord(item[3]) - ord('a'))
    
            for item in uneuqal:
                if find(ord(item[0]) - ord('a')) == find(ord(item[3]) - ord('a')):
                    return False
            return True

转载于:https://www.cnblogs.com/seyjs/p/10364720.html