Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4and 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 <= 500equations[i].length == 4-
equations[i][0]andequations[i][3]are lowercase letters -
equations[i][1]is either'='or'!' -
equations[i][2]is'='
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
示例 1：
输入：["a==b","b!=a"] 输出：false 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：
输出：["b==a","a==b"] 输入：true 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：
输入：["a==b","b==c","a==c"] 输出：true
示例 4：
输入：["a==b","b!=c","c==a"] 输出：false
示例 5：
输入：["c==c","b==d","x!=z"] 输出：true
提示：
1 <= equations.length <= 500equations[i].length == 4-
equations[i][0]和equations[i][3]是小写字母 -
equations[i][1]要么是'='，要么是'!' -
equations[i][2]是'='
Runtime: 48 ms
Memory Usage: 4 MB
1 class Solution {
2 func equationsPossible(_ equations: [String]) -> Bool {
3 var ds:DJSet = DJSet(26)
4 for e in equations
5 {
6 if e[1] == "="
7 {
8 var l:Int = e[0].ascii - 97
9 var r:Int = e[3].ascii - 97
10 ds.union(l,r)
11 }
12 }
13 for e in equations
14 {
15 if e[1] == "!"
16 {
17 var l:Int = e[0].ascii - 97
18 var r:Int = e[3].ascii - 97
19 if ds.equiv(l,r)
20 {
21 return false
22 }
23 }
24 }
25 return true
26 }
27 }
28
29 extension String {
30 //subscript函数可以检索数组中的值
31 //直接按照索引方式截取指定索引的字符
32 subscript (_ i: Int) -> Character {
33 //读取字符
34 get {return self[index(startIndex, offsetBy: i)]}
35 }
36 }
37
38 extension Character
39 {
40 //属性：ASCII整数值(定义小写为整数值)
41 var ascii: Int {
42 get {
43 let s = String(self).unicodeScalars
44 return Int(s[s.startIndex].value)
45 }
46 }
47 }
48
49 public class DJSet
50 {
51 var upper:[Int]
52
53 init(_ n:Int)
54 {
55 upper = [Int](repeating:-1,count:n)
56 }
57
58 func root(_ x:Int) -> Int
59 {
60 if(upper[x] < 0)
61 {
62 return x
63 }
64 else
65 {
66 upper[x] = root(upper[x])
67 return upper[x]
68 }
69 }
70
71 func equiv(_ x:Int,_ y:Int) -> Bool
72 {
73 return root(x) == root(y)
74 }
75
76 func union(_ x:Int,_ y:Int) -> Bool
77 {
78 var x:Int = root(x)
79 var y:Int = root(y)
80 if x != y
81 {
82 if upper[y] < upper[x]
83 {
84 var d:Int = x
85 x = y
86 y = d
87 }
88 upper[x] += upper[y]
89 upper[y] = x
90 }
91 return x == y
92 }
93
94 func count() -> Int
95 {
96 var ct:Int = 0
97 for u in upper
98 {
99 if u < 0
100 {
101 ct += 1
102 }
103 }
104 return ct
105 }
106 }