Leetcode 990 Satisfiablitity of Equality Equations

发表于 |

给定一系列字符串来表示两个变量之间的关系，每个字符串固定为4长度，并且是以下两种表现形式：

  1. “a==b”
  2. “a!=b”
    这里的a,b只是示例。
    返回true如果所有变量之间的关系都可以符合！

示例 1:
输入: [“a==b”,”b!=a”]
输出: false
解释: 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.

示例 2:
输入: [“b==a”,”a==b”]
输出: true
解释: We could assign a = 1 and b = 1 to satisfy both equations.

示例 3:
输入: [“a==b”,”b==c”,”a==c”]
输出: true
示例 4:
输入: [“a==b”,”b!=c”,”c==a”]
输出: false

示例 5:
输入: [“c==c”,”b==d”,”x!=z”]
输出: 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 ‘=’

思路分析：
这道题有点染色法的意思，我先根据给定的式子中的相等式将图画出来，然后使用dfs将所有相连的节点付成相同的值。

然后根据给定的式子中的不等式判断这些不该相等的节点值中是否有相同的值。

变量意义：

  1. d用来存储每个节点对应的节点值
  2. G用来存储图
  3. N用来存储不等关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def equationsPossible(self, equations):
        d = collections.defaultdict(int)
        G = collections.defaultdict(list)
        N = collections.defaultdict(list)
        val = 1
        # 构造图
        for equal in equations:
            v1, v2, v3, v4 = equal
            if v2 == '=':
                G[v1].append(v4)
                G[v4].append(v1)
            else:
                if v1 == v4: return False
                N[v1].append(v4)
                N[v4].append(v1)
        
        # dfs方法给相连节点赋值
        vis = set()
        def dfs(node, val):
            for nex in G[node]:
                if nex in vis: continue
                if nex in d and d[nex] != val: return False
                vis.add(nex)
                d[nex] = d[node]
                if not dfs(nex, val): return False
            return True
        
        for key in G:
            if key in vis: continue
            vis.add(key)
            d[key] = val
            if not dfs(key, val): return False
            val += 1
        
        # 判断不等关系是否都成立
        for key in N:
            if key not in d: continue
            for nex in N[key]:
                if nex in d and d[nex] == d[key]: return False
        return True