“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

You are given a string s and an array of “index pairs” in that string, pairs[I] = [a, b] representing two indexes (numbered from 0) in the string.

You can swap characters at any pair of indexes in pairs as many times as you want.

Returns the smallest lexicographical string that s can become after a number of swaps.

Example 1:

Input: s = "dcab", pairs = [[0, 3], [1, 2]] output: "bacd" explanation: exchange s [0] and [3] s, s = "bcad exchange" s [1] and [2] s, s = "bacd"Copy the code

Example 2:

Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]] output: "abcd" explanation: Swap s[0] and S [3], s = "bcad" swap S [0] and S [2], s = "ACbd" swap S [1] and S [2], s = "ABCD"Copy the code

Example 3:

Input: s = "cba", pairs = [[0, 1], [1, 2]] output: "ABC" explanation: Exchange s [0] and [1] s, s = "bca exchange" s [1] and [2] s, s = "bac" exchange s [0] and [1] s, s = "ABC"Copy the code

Tip:

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • sContains only lowercase English letters

Their thinking

  • This topic examines the knowledge point is more
  • We use union to look up sets to find elements that can be replaced with each other at will
  • withmapObject to record elements that can be replaced at will
  • Sort the replaceable elements
  • Defines an object to record the return valuestrTo traverse thes
  • To find outsFill each term with the smallest letter that can be used to replace itstrIn the

The problem solving code

var smallestStringWithSwaps = function(s, pairs) {
    if(! pairs.length)return s
    const union = new UnionFind(s.length)
    for(let [x,y] of pairs){
        union.merge(x,y)
    }
    const map = {}
    for(let i = 0; i<s.length; i++ ){const parent = union.find(i)
        if(! map[parent]) map[parent] = [] map[parent].push(s[i]) }for(let i in map){
        map[i].sort((a,b) = > b.charCodeAt(0) - a.charCodeAt(0))}let str = ' '
    for(let i=0; i<s.length; i++){const parent = union.find(i)
        str += map[parent].pop()
    }
    return str

};

class UnionFind {
    constructor(len){
        this.parents = new Array(len).fill(0).map((v,i) = >i)
        this.rank =  new Array(len).fill(0)}find(i){
        if(this.parents[i] == i ) return i
        return this.find(this.parents[i])
    }
    connect(a,b){
        return this.find(a) == this.find(b)
    }
    merge(a,b){
        if(this.connect(a,b)) return
        this.parents[this.find(a)] = this.find(b)
    }
}
Copy the code

Running through the code, we see that we’re out of time.

To do this, we optimize the merge logic to move a small number of nodes to a large number of nodes at a time.

merge(a,b){
    if(this.connect(a,b)) return
    const fa = this.find(a)
    const fb = this.find(b)
    if(this.rank[fa]>this.rank[fb]){
        this.parents[fb] = fa
    }else{
        this.parents[fa] = fb
        if(this.rank[fa]==this.rank[fb] ){
            this.rank[fb]++
        }
    }
}
Copy the code

If you have any questions or suggestions, please leave a comment!