题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一系列 == 或者 != 的等式或不等式，左右两侧会是小写字母的变量，求所有式子是否不矛盾。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        parent = list(range(27))
        def find(i:int) -> int:
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
        
        def union(i:int, j:int):
            parent[find(i)] = parent[find(j)]
        
        other_index = []
        for i, equation in enumerate(equations):
            if equation[1] == "=":
                a = ord(equation[0]) - 97
                b = ord(equation[-1]) - 97
                union(a, b)
            else:
                other_index.append(i)
        
        for i in other_index:
            equation = equations[i]
            a = ord(equation[0]) - 97
            b = ord(equation[-1]) - 97
            if find(a) == find(b):
                return False

        return True