按字典序排列最小的等效字符串 图解题解

等价字母归成类，baseStr 换成同类里最小的谁

给两个等长字符串 s1 和 s2，位置对齐看，s1[i] 和 s2[i] 是一组等价字母，等价会传递：a 跟 b、b 跟 c 同组，a 跟 c 也同组。把能连起来的字母归成一类，再把 baseStr 每个字母换成同类里最小的那个，返回换完的串。题面例子 s1="abc"、s2="cde"、baseStr="eed"，连出 {a,c,e} 和 {b,d} 两类，eed 换成 aab。

挨个把字母连上线，为什么还是理不清谁跟谁

字母两两配对不难，难在它们连成的关系网：c 这步跟 a 连、下步又跟 e 连，只攥着一串线，很难随时答出 e 该换成谁。尤其传递：第 2 列把 e 拉进来时，得先知道 e 早跟 a、c 是一家，这层关系埋在前几步里，顺着线爬才理得清。

并查集把同一类字母收到一个根底下

这种反复把元素两两归组、又要随时查两个在不在同一组的场景，正对上并查集，一种专管分组的结构。它给每个元素记一个父亲，顺着父亲走到头，指向自己的那个就是根，同组成员最后都落在同一个根上。

这题只有 26 个字母，开一个长 26 的父亲数组，起初每个字母的父亲都是自己。合并有个死约定：两字母并组时先各自找到根，让大的根挂到小的根下，永远小的当根。参考代码里比较两个根 px 和 py，px＜py 就让 p[py] 指向 px。爬到顶的根恰好是这组最小字母，替换时直接换成根。

先 find 到根，再连根，永远小的坐根

分两趟。建组这趟把 s1、s2 逐列对齐，每列两字母合并一次：各自 find 到根，比字母大小让大的挂到小的下面。要点是合并两个根、不是原字母：某字母可能早并进别的组，先 find 到根才知道它归谁。替换这趟扫 baseStr，每个字母 find 到根，把根写进答案拼起来即结果。

拿 abc、cde、eed 把两趟完整推一遍

先建组。第 0 列 a 配 c，a 小让 c 指向 a，得 {a,c}、根 a。第 1 列 b 配 d，b 小让 d 指向 b，得 {b,d}、根 b。第 2 列 c 配 e：c 的父亲已是 a，find 上去根是 a、不是 c，e 的根还是 e，真正要连的是 a 和 e；a 小让 e 指向 a，c、e 都挂到 a 底下，第一组 {a,c,e}、根 a，另一组 {b,d}、根 b。

再换 baseStr="eed"。第 0 位 e，find 到根 a，写 a；第 1 位还是 e，根仍是 a，写 a；第 2 位 d，find 到根 b，写 b。拼成 "aab"。每组根都是组里最小字母，换出来的串每位都最小，字典序自然最小。

26 个字母撑起的常数空间，选根找根都别偷懒

设 s1 长 n、baseStr 长 m：建组 n 次合并、替换 m 次查询，find 带路径压缩后每次近似常数，合起来 O((n+m)·α)，α 近似常数；父亲数组固定 26 格，空间 O(1)。选根松不得：随手挑或按树高选根，字母虽连通根却未必最小，字典序最小就丢了，只能认字母大小让小的坐根。找根也别省：合并替换都得 find 到最终的根，只看一层父亲会停在中间字母上，写进答案的就不是最小字母。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(26))
        for a, b in zip(s1, s2):
            x, y = ord(a) - ord("a"), ord(b) - ord("a")
            px, py = find(x), find(y)
            if px < py:
                p[py] = px
            else:
                p[px] = py
        return "".join(chr(find(ord(c) - ord("a")) + ord("a")) for c in baseStr)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<int> p(26);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&]( int x ) -> int {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        };
        for (int i = 0; i < s1.length(); ++i) {
            int x = s1[i] - 'a';
            int y = s2[i] - 'a';
            int px = find(x), py = find(y);
            if (px < py) {
                p[py] = px;
            } else {
                p[px] = py;
            }
        }
        string s;
        for (char c : baseStr) {
            s.push_back('a' + find(c - 'a'));
        }
        return s;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private final int[] p = new int[26];

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
        }
        for (int i = 0; i < s1.length(); ++i) {
            int x = s1.charAt(i) - 'a';
            int y = s2.charAt(i) - 'a';
            int px = find(x), py = find(y);
            if (px < py) {
                p[py] = px;
            } else {
                p[px] = py;
            }
        }
        char[] s = baseStr.toCharArray();
        for (int i = 0; i < s.length; ++i) {
            s[i] = (char) ('a' + find(s[i] - 'a'));
        }
        return String.valueOf(s);
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}