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

这道题到底在问什么

输入

s1="abc", s2="cde", baseStr="eed"

输出

"aab" (分组 [a,c,e] 和 [b,d])

输入

s1="hello", s2="world", baseStr="hold"

输出

"hdld" (只有 o 变成 d)

最优解：一步一步想明白

1. 3记住这个约定:合并两类时,大字母指向小字母,小的当根。下面每一帧都在套它。
2. 4等价类个数 = 5先把例子里出现的 5 个字母 a、b、c、d、e 摆出来。一开始谁也不连谁,每个字母自己是一类,所以等价类个数是 5。接下来按 s1、s2 一列一列地合并。
3. 5s1="abc" s2="cde"s1 和 s2 对齐看:第 0 列 a 配 c、第 1 列 b 配 d、第 2 列 c 配 e。也就是要把 a 和 c、b 和 d、c 和 e 分别连起来。一列一列处理。
4. 6准备合并 a 和 c看第 0 列:s1 的 a 和 s2 的 c 等价。先紫色点亮这两个字母,准备把它们并到一类。
5. 7代表 a 与 c合并前先各自找代表元(也就是树根)。现在 a 的根是 a、c 的根是 c,两个都还是自己,谁也没被合并过。
6. 8等价类个数 = 4a 比 c 小,按约定小的当根,所以让 c 指向 a。现在 a 和 c 同一类、根是 a。等价类个数从 5 降到 4。
7. 9准备合并 b 和 d看第 1 列:s1 的 b 和 s2 的 d 等价。点亮 b 和 d,准备合并。
8. 10代表 b 与 db 的根是 b、d 的根是 d,都还独立。它们和左边那组没关系,是另一棵树。
9. 11等价类个数 = 3b 比 d 小,让 d 指向 b,根是 b。现在有两组:{a,c} 和 {b,d}。等价类个数降到 3。
10. 12准备合并 c 和 e看第 2 列:s1 的 c 和 s2 的 e 等价。注意 c 之前已经和 a 一类了,这一步会把 e 也拉进来,传递性就体现在这。
11. 13代表 a 与 e关键一步:找 c 的根,c 指向 a,所以 c 的根是 a,不是 c。e 还是自己。所以真正要合并的是代表 a 和代表 e,而不是 c 和 e。
12. 14等价类个数 = 2a 比 e 小,让 e 指向 a。现在 e、c 都挂在 a 下面,a 这一类成了 {a,c,e}。等价类个数降到 2。
13. 15a 是这类最小字母回看这棵树:c 指 a、e 指 a,a 自己是根。a 是 {a,c,e} 里字典序最小的,正因为每次合并都让小字母当根,根天然就是这一类的最小值。
14. 16{a,c,e}→a {b,d}→b三列处理完,字母分成两类:{a,c,e} 都映射到 a,{b,d} 都映射到 b。这张映射表就是替换 baseStr 的依据。
15. 17逐字查根并替换并查集建好了,现在处理 baseStr="eed"。逐个字母查它的根,把根写下来,拼成答案。
16. 18找 e 的根第 0 个字母是 e。去并查集里查 e 的根:e 指向 a,a 是根。
17. 19已拼出 "a"e 的根是 a,所以第 0 位写 a。目前答案是 "a"。
18. 20又是 e第 1 个字母还是 e,根同样是 a,不用重新推。
19. 21已拼出 "aa"第 1 位也写 a。答案变成 "aa"。
20. 22找 d 的根第 2 个字母是 d。查 d 的根:d 指向 b,b 是根。它属于另一组 {b,d}。
21. 23已拼出 "aab"d 的根是 b,所以第 2 位写 b。答案现在是 "aab"。
22. 24eed → aab三个字母都替换完:e→a、e→a、d→b,baseStr "eed" 变成 "aab"。因为每一类的根都是它的最小字母,这样换出来的串字典序一定最小。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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;
    }
};

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];
    }
}

复杂度

面试官可能追问