[Swift]LeetCode839.相似字符串组|SimilarStringGroups

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10579363.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Note:

A.length <= 2000
A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.

如果我们交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

我们给出了一个不包含重复的字符串列表 A。列表中的每个字符串都是 A 中其它所有字符串的一个字母异位词。请问 A 中有多少个相似字符串组？

示例：

输入：["tars","rats","arts","star"]
输出：2

提示：

A.length <= 2000
A[i].length <= 1000
A.length * A[i].length <= 20000
A 中的所有单词都只包含小写字母。
A 中的所有单词都具有相同的长度，且是彼此的字母异位词。
此问题的判断限制时间已经延长。

备注：

字母异位词[anagram]，一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

Time Limit Exceeded

  1 class Solution {
  2     func numSimilarGroups(_ A: [String]) -> Int {
  3         var A = A
  4         if A.isEmpty {return 0}
  5         if A[0].count < 20 {return help2(&A)}
  6         else{ return help1(&A)}
  7     }
  8     
  9     func check(_ str1:String,_ str2:String) -> Bool
 10     {
 11         let len:Int = str1.count
 12         var cnt:Int = 0
 13         var arr1:[Character] = Array(str1)
 14         var arr2:[Character] = Array(str2)
 15         for i in 0..<len
 16         {
 17             if arr1[i] != arr2[i]
 18             {
 19                 cnt += 1
 20                 if cnt > 2
 21                 {
 22                     return false
 23                 }
 24             }
 25         }
 26         return true
 27     }
 28     
 29     func find(_ x:Int,_ p:inout [Int]) -> Int
 30     {
 31         if x != p[x]
 32         {
 33             p[x] = find(p[x],&p)
 34         }
 35         return p[x]
 36     }
 37     
 38     func help1(_ A:inout [String]) -> Int
 39     {
 40         let n:Int = A.count
 41         var fa:[Int] = [Int]()
 42         for i in 0..<n
 43         {
 44             fa.append(i)
 45         }
 46         for  i in 0..<n
 47         {
 48             for j in (i + 1)..<n
 49             {
 50                 if check(A[i] ,A[j])
 51                 {
 52                     let num:Int = find(i,&fa)
 53                     fa[num] = find(j,&fa)
 54                 }
 55             }
 56         }
 57         var ans:Int = 0
 58         for i in 0..<fa.count
 59         {
 60             if fa[i] == i
 61             {
 62                 ans += 1
 63             }
 64         }
 65         return ans
 66     }
 67     
 68     func help2(_ A:inout [String]) -> Int
 69     {
 70         var sA:Set<String> = Set(A)
 71         var q:[String] = [String]()
 72         var n:Int = 0
 73         while(!sA.isEmpty)
 74         {
 75             q.append(sA.removeFirst())
 76             n += 1
 77             while(!q.isEmpty)
 78             {
 79                 var s:String = q.first!
 80                 q.removeFirst()
 81                 let len:Int = s.count      
 82                 var arr:[Character] = Array(s)
 83                 for i in 0..<len
 84                 {                 
 85                     for j in (i + 1)..<len
 86                     {
 87                         if arr[i] != arr[j]
 88                         {
 89                             var arrS = arr
 90                             arrS.swapAt(i, j)
 91                             let str:String = String(arrS)
 92                             if sA.contains(str)
 93                             {
 94                                 q.append(str)
 95                                 sA.remove(str)
 96                             }
 97                             if sA.isEmpty {return n}
 98                         }
 99                     }
100                 }
101             }
102         }
103         return n
104     }
105 }

Time Limit Exceeded

 1 class Solution {
 2     func numSimilarGroups(_ A: [String]) -> Int {
 3         var A = A
 4         var countA:Int = A.count
 5         if countA < 2 {return countA}
 6         var res:Int = 0
 7         for i in 0..<countA
 8         {
 9             if A[i].isEmpty {continue}
10             var str:String = A[i]
11             A[i] = String()
12             res += 1
13             dfs(&A,str)
14         }
15         return res
16     }
17     
18     func dfs(_ arr:inout [String],_ str:String)
19     {
20         for i in 0..<arr.count
21         {
22             if arr[i].isEmpty {continue}
23             if helper(str,arr[i])
24             {
25                 var s:String = arr[i]
26                 arr[i] = String()
27                 dfs(&arr,s)
28             }
29         }
30     }
31 
32     func helper(_ s:String,_ t:String) -> Bool
33     {
34         var arrS:[Character] = Array(s)
35         var arrT:[Character] = Array(t)
36         var res:Int = 0
37         var i:Int = 0
38         while(res <= 2 && i < s.count)
39         {
40             if arrS[i] != arrT[i]
41             {
42                 res += 1
43             }
44             i += 1
45         }
46         return res == 2
47     }
48 }
49 
50

Time Limit Exceeded

 1 class Solution {
 2     func numSimilarGroups(_ A: [String]) -> Int {
 3         var uf:UnionFind = UnionFind(A.count)
 4         let countA:Int = A.count
 5         for i in 0..<countA
 6         {
 7             for j in (i + 1)..<countA
 8             {                
 9                 if isSimilar(A[i], A[j])
10                 {
11                     uf.union(i,j)
12                 }
13             }
14         }
15         return uf.getSize()
16     }
17 
18     func isSimilar(_ a:String,_ b:String) -> Bool
19     {
20         var arrA:[Character] = Array(a)
21         var arrB:[Character] = Array(b)
22         var count:Int = 0
23         var num:Int = arrA.count > arrB.count ? arrA.count : arrB.count
24         for i in 0..<num
25         {            
26             if arrA[i] != arrB[i] && ++count > 2
27             {
28                 return false
29             }
30         }
31         return true
32     }
33 }
34 
35 /*扩展Int类，实现自增++运算符*/
36 extension Int{
37     //++前缀:先自增再执行表达示
38     static prefix func ++(num:inout Int) -> Int {
39         //输入输出参数num
40         num += 1
41         //返回加1后的数值
42         return num
43     }
44 }
45 
46 class UnionFind
47 {
48     var sets:[Int]
49     var size:Int
50 
51     init(_ size:Int)
52     {
53         self.sets = [Int](repeating:0,count:size)
54         self.size = size
55         for i in 0..<size
56         {
57             sets[i] = i
58         }
59     }
60 
61     func union(_ i:Int,_ j:Int)
62     {
63         var u:Int = find(sets, i)
64         var v:Int = find(sets, j)
65         if(u != v){
66             sets[u] = v
67             size -= 1
68         }
69     }
70 
71     func find(_ sets:[Int],_ v:Int) -> Int
72     {
73         return sets[v] == v ? v : find(sets, sets[sets[v]])
74     }    
75 
76     func getSize() -> Int
77     {
78         return size
79     }
80 }