[Swift]LeetCode1202.交换字符串中的元素|SmallestStringWithSwaps

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

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

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

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

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

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

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以任意多次交换在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"

示例 3：

输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"

提示：

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

968ms

 1 class Solution {
 2     func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
 3         let s = Array(s)
 4         var res = [Character](repeating: "a", count: s.count)
 5         var uf = UnionFind(s.count)
 6         for pair in pairs {
 7             uf.union(pair[0], pair[1])
 8         }
 9         var _comps = [Int: [Character]]()
10         for (i, char) in s.enumerated() {
11             let parent = uf.find(i)
12             _comps[parent, default: []].append(char)
13         }
14         var comps = [Int: Queue]()
15         for (k, v) in _comps {
16             let newV = v.sorted()
17             comps[k] = Queue(newV)
18         }
19         for i in 0..<s.count {
20             let parent = uf.find(i)
21             let comp = comps[parent]!
22             res[i] = comp.remove()
23         }
24         return String(res)
25     }
26 }
27 
28 class Queue {
29     let arr: [Character]
30     var index = 0
31     
32     init(_ arr: [Character]) {
33         self.arr = arr
34     }
35     
36     func remove() -> Character {
37         let res = arr[index]
38         index += 1
39         return res
40     }
41 }
42 
43 struct UnionFind {
44     var arr: [Int]
45     var size: [Int]
46     
47     init(_ n: Int) {
48         arr = [Int](repeating: 0, count: n)
49         for i in 0..<n {
50             arr[i] = i
51         }
52         size = [Int](repeating: 1, count: n)
53     }
54     
55     mutating func union(_ a: Int, _ b: Int) -> Bool {
56         let rootA = find(a)
57         let rootB = find(b)
58         if rootA == rootB { return false }
59         if size[rootA] > size[rootB] {
60             arr[rootB] = rootA
61             size[rootA] += size[rootB]
62         } else {
63             arr[rootA] = rootB
64             size[rootB] += size[rootA]
65         }
66         return true
67     }
68     
69     mutating func find(_ a: Int) -> Int {
70         var a = a
71         while arr[a] != a {
72             arr[a] = arr[arr[a]]
73             a = arr[a]
74         }
75         return a
76     }
77 }

1184ms

 1 class Solution {
 2     var roots = [Int]()
 3     var ranks = [Int]()
 4     func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
 5         var chars = Array(s)
 6         (0...chars.count-1).forEach{ roots.append($0) }
 7         ranks = Array(repeating: 1, count: s.count)
 8         
 9         for pair in pairs {
10             union(pair[0], pair[1])
11         }
12         
13         var dict1 = [Int: [Int]]()
14         var dict2 = [Int: [Character]]()
15         
16         
17         for i in roots.indices {
18             find(i)
19         }
20         
21         
22         for i in roots.indices {
23             dict1[roots[i], default: [Int]()].append(i)
24             dict2[roots[i], default: [Character]()].append(chars[i])
25         }
26         for (key, indices) in dict1 {
27             if indices.count > 1 {
28                 let arr = dict2[key]!.sorted()
29                 var curr = 0 
30                 for idx in indices {
31                     chars[idx] = arr[curr]
32                     curr += 1
33                 }
34             }
35         }
36         
37         return String(chars)
38     }
39     
40     fileprivate func union(_ x: Int, _ y: Int) -> Bool {
41         let xRoot = find(x)
42         let yRoot = find(y)
43         
44         if xRoot == yRoot {
45             return false
46         }
47         if ranks[xRoot] > ranks[yRoot] {
48             roots[yRoot] = xRoot
49         } else if ranks[xRoot] < ranks[yRoot] {
50             roots[xRoot] = yRoot
51         } else {
52             ranks[xRoot] += 1
53             roots[yRoot] = xRoot
54         }
55         
56         return true
57     }
58     
59     fileprivate func find(_ current: Int) -> Int {
60         var path = [Int]()
61         var current = current
62         while roots[current] != current {
63             path.append(current)
64             current = roots[current]
65         }
66         
67         for p in path {
68             roots[p] = current
69             ranks[p] == 1
70         }
71         ranks[current] = 2
72         return current
73     }
74 }

1408ms

 1  class Solution {
 2     func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
 3                var indices = [Int]()                                                //Stored indices of same group
 4         var visited = [Bool](repeating: false, count: s.count)
 5         var adjList = [[Int]](repeating: [Int](), count: s.count)
 6         var indiceString = ""                                                 //Stores  string formed by indices in the same group
 7         func dfs(_ chars: [Character], _ n: Int) {                            //DFS to get all indices in same group
 8             visited[n] = true
 9             indices.append(n)
10             indiceString += "\(chars[n])"
11             for i in adjList[n] where !visited[i] {
12                 dfs(chars, i)
13             }
14         }
15 
16         for pair in pairs {
17             adjList[pair[0]].append(pair[1])
18             adjList[pair[1]].append(pair[0])
19         }
20 
21         var chars = Array(s)
22         for i in chars.indices {
23             indiceString = "" //Clear string formed by one group of indices before finding next group
24             indices.removeAll() //clear indices vector before finding another group
25             dfs(chars, i)
26             let indiceStringChars = indiceString.sorted() //Sort the string in same group
27             //Sort the indices in the same group
28             indices = indices.sorted()
29 
30             for i in indices.indices { //Replace all the indices in the same group with the sorted character replacement
31                 chars[indices[i]] = indiceStringChars[i]
32             }
33         }
34         return String(chars)
35     }
36 }

Runtime: 4484 ms

Memory Usage: 36.6 MB

 1 class Solution {
 2     func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
 3         var s:[Character] = Array(s)
 4         let n:Int = s.count
 5         let unionFind = UnionFind(size: n, count: n)
 6         for p in pairs
 7         {
 8             unionFind.union(p[0], p[1])
 9         }
10         var components:[[Int]] = [[Int]](repeating:[Int](),count:n)
11         for i in 0..<n
12         {
13             components[unionFind.find(i)].append(i)
14         }
15         for component in components
16         {
17             var chars:[Character] = [Character]()
18             for index in component
19             {
20                 chars.append(s[index])
21             }
22             chars.sort()
23             for i in 0..<component.count
24             {
25                 s[component[i]] = chars[i]
26             }
27         }
28         return String(s)
29     }
30 }
31 
32 class UnionFind {
33     private var parent: [Int]
34     private (set) var count = 0
35     
36     init(size: Int, count: Int) {
37         self.parent = Array(0..<size)
38         self.count = count
39     }
40 
41     func union(_ x: Int, _ y: Int) {
42         let px = find(x)
43         let py = find(y)
44         if px != py {
45             parent[px] = py
46             count -= 1
47         }
48     }
49 
50     func find(_ x: Int) -> Int {
51         if parent[x] == x {
52             return x
53         }
54         parent[x] = find(parent[x])
55         return parent[x]
56     }
57 }