Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

1202. Exchange elements in a string

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

Train of thought

This problem is also a more typical and search set of problems, we can be divided into several steps to deal with.

  1. Iterate through the association array to suggest the association relationship;
  2. Iterating through a string, grouping the data under the same association into an array, usingmapRecord;
  3. traversemap, sort the array of each associated relationship;
  4. Iterate over the initialization node frommapTake out the result of construction one by one.

Tipping site

/ * * *@param {string} s
 * @param {number[][]} pairs
 * @return {string}* /
var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const uf = new UnionFind(n);

    // join all related items together
    for (let i = 0; i < pairs.length; i++) {
        const [ a, b ] = pairs[i];
        uf.merge(a, b);
    }

    // enumerate all collections
    let map = new Map(a);for (let i = 0; i < n; i++) {
        const index = uf.find(i);
        let cur = map.get(index) || [];
        map.set(index, [...cur, s[i]]);
    }

    // Sort the enumerated values
    for (let [ key, value ] of map) {
        value.sort((a, b) = > a.charCodeAt() - b.charCodeAt());
    }

    // Returns the result, the value of each node is accumulated
    let result = "";
    for (let i = 0; i < n; i++) {
        let cur = map.get(uf.parent[i]);
        result += cur.shift();
        map.set(uf.parent[i], cur);
    }

    return result;
};

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

We don’t have a nested structure, but it’s a bit of a performance drain when the map is constantly evaluating and assigning values, so let’s see if we can skip this step and see if we can do it directly through arrays. Think about ways to optimize your code to make it elegant.

To optimize the

/ * * *@param {string} s
 * @param {number[][]} pairs
 * @return {string}* /
var smallestStringWithSwaps = function(s, pairs) {
    const n = s.length;
    const uf = new UnionFind(n);

    // join all related items together
    for (let i = 0; i < pairs.length; i++) {
        const [ a, b ] = pairs[i];
        uf.merge(a, b);
    }

    // enumerate all collections
    let list = new Array(n).fill(0).map(v= > new Array());
    for (let i = 0; i < n; i++) {
        const index = uf.find(i);
        list[index].push(s[i]);
    }

    
    // Sort the enumerated values
    for (let i = 0; i < n; i++) {
        list[i].sort((a, b) = > b.charCodeAt() - a.charCodeAt());
    }

    // Returns the result, the value of each node is accumulated
    let result = "";
    for (let i = 0; i < n; i++) {
        const index = uf.find(i);
        result += list[index].pop();
    }

    return result;
};

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.