1202.交换字符串中的元素

链接：1202.交换字符串中的元素
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串、排序
简介：给你一个字符串 s,返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

题解 1 - typescript

• 编辑时间：2021-05-01
• 执行用时：236ms
• 内存消耗：67.1MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function smallestStringWithSwaps(s: string, pairs: number[][]): string {
  const len = s.length;
  const uf = new UnionFind(len);
  pairs.forEach(([i1, i2]) => uf.union(i1, i2));
  const map: Record<number, number[]> = {};
  for (let i = 0; i < len; i++) {
    const index = uf.find(i);
    let list = map[index];
    if (!list) list = map[index] = [];
    list.push(i);
  }
  const lists = Object.values(map);
  const cache = s.split('');
  let ans = s.split('');
  for (const list of lists) {
    const sorted = list.slice().sort((i1, i2) => s[i1].codePointAt(0)! - s[i2].codePointAt(0)!);
    for (let i = 0, l = list.length; i < l; i++) {
      ans[list[i]] = cache[sorted[i]];
    }
  }
  return ans.join('');
}