• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. A.length <= 2000
  2. A[i].length <= 1000
  3. A.length * A[i].length <= 20000
  4. All words in A consist of lowercase letters only.
  5. All words in A have the same length and are anagrams of each other.
  6. 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

提示:

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

备注:

      字母异位词[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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode322.零钱兑换|CoinChange发布时间:2022-07-14
下一篇:
1.3 Swift语言中的常量和变量 [Swift原创教程]发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap