[Swift Weekly Contest 123]LeetCode990. 等式方程的可满足性 | Satisfiability of Equality Equations

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: falseExplanation: 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: trueExplanation: 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 '='

---

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0] 和 equations[i][3] 是小写字母
4. equations[i][1] 要么是 '='，要么是 '!'
5. 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 < 0100             {101                 ct  = 1102             }103         }104         return ct105     }106 }

 

来源：http://www.icode9.com/content-4-112251.html