1202. Smallest String With Swaps

Leetcode link

解题思路

题目给了我们一个字符串，并且给了多个可以多次交换的字符串下标，要求我们经过一连串交换之后返回字典序最小的字符串。

首先我们需要知道一件事：交换是有传递性的。

也就是说，如果有可交换下标 [a,b] 与[b,c]，那么 a 与 c 也是可以交换的（通过 b）

所以，我们可以把所有可以互相交换的字符下标收集起来，称为一个组。

将所有的字符下标都收集完了之后，我们对每个组内都以字典序排序，然后按照顺序放回原来在的下标，就是题目所求了。

针对上面的思路，我们使用并查集数据结构。

C++

class UnionFind {
 private:
  vector<int> root;
  vector<int> rank;

 public:
  UnionFind(int size) : root(size), rank(size) {
    for (int i = 0; i < size; i++) {
      root[i] = i;
      rank[i] = 1;
    }
  }

  int find(int x) {
    if (x == root[x]) {
      return x;
    }
    return root[x] = find(root[x]);
  }

  void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] >= rank[rootY]) {
        root[rootY] = rootX;
        rank[rootX] += rank[rootY];
      } else {
        root[rootX] = rootY;
        rank[rootY] += rank[rootX];
      }
    }
  }
};

class Solution {
 public:
  string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
    int n = s.size();
    UnionFind uf(n);

    // 给所有字符分组（保存下标）
    for (auto& edge : pairs) {
      uf.unionSet(edge[0], edge[1]);
    }

    //   建立组长->组员的映射（保存下标）
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) {
      int root = uf.find(i);
      groups[root].push_back(i);
    }

    string result(n, ' ');
    for (auto& group : groups) {
      // 取得组员的下标
      vector<int> indics = group.second;

      // 把每一组的成员按照字典顺序排列
      vector<char> chars;
      for (int index : indics) {
        chars.push_back(s[index]);
      }
      sort(chars.begin(), chars.end());

      // 把排列好的字符放回对应的位置
      for (int i = 0; i < indics.size(); i++) {
        result[indics[i]] = chars[i];
      }
    }

    return result;
  }
};

Javascript

class UnionFind {
    constructor(size) {
        this.root = new Array(size);
        this.rank = new Array(size);
        for (let i = 0; i < size; i++) {
            this.root[i] = i;
            this.rank[i] = 1;
        }
    }

    find(x) {
        if (x == this.root[x]) {
            return x;
        }
        return (this.root[x] = this.find(this.root[x]));
    }

    unionSet(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX != rootY) {
            if (this.rank[rootX] >= this.rank[rootY]) {
                this.root[rootY] = rootX;
                this.rank[rootX] += this.rank[rootY];
            } else {
                this.root[rootX] = rootY;
                this.rank[rootY] += this.rank[rootX];
            }
        }
    }
}

var smallestStringWithSwaps = function (s, pairs) {
    const n = s.length;
    const uf = new UnionFind(n);

    // 给所有字符分组（保存下标）
    for (let edge of pairs) {
        uf.unionSet(edge[0], edge[1]);
    }

    //   建立组长->组员的映射（保存下标）
    let groups = {};
    for (let i = 0; i < n; i++) {
        let root = uf.find(i);
        groups[root] === undefined && (groups[root] = []);
        groups[root].push(i);
    }

    let result = new Array(n);
    for (let key in groups) {
        // 取得组员的下标数组
        let indics = groups[key];

        // 把每一组的成员按照字典顺序排列
        let chars = [];
        for (let index of indics) {
            chars.push(s[index]);
        }
        chars.sort((a, b) => a.charCodeAt('0') - b.charCodeAt('0'));

        // 把排列好的字符放回对应的位置
        for (let i = 0; i < indics.length; i++) {
            result[indics[i]] = chars[i];
        }
    }

    return result.join('');
};