[LeetCode] 每日一题 1061. 按字典序排列最小的等效字符串（并查集）

题目描述

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中  s1[i] 和 s2[i]  是一组等价字符。

• 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

•  自反性 ：'a' == 'a'

•  对称性 ：'a' == 'b' 则必定有 'b' == 'a'

•  传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

题目链接

https://leetcode.cn/problems/lexicographically-smallest-equivalent-string

示例输入

示例 1

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

示例 2

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

提示

• 1 <= s1.length, s2.length, baseStr <= 1000

• s1.length == s2.length

• 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。

解题思路

今天这题一看描述就让人想到——并查集😎😎

题目提供了两个字符串 s1 和 s2，表示对应位置上的字符是等价的。并且这种等价关系满足自反性、对称性和传递性，这正是并查集的经典应用场景：维护多个集合的合并与查找关系

思路很清晰：

• 每个小写字母可以看作一个节点，总共26个

• 对于 s1[i] == s2[i] 的关系，我们将对应的两个字符所在的集合合并

• 合并的策略是：永远把字典序小的字符作为整个集合的代表，这样后续替换时才能保证最终字符串是字典序最小

• 最后对 baseStr 中每个字符进行“查询替换”，用其等价集合中最小的字符来代替

这类题目如果熟悉并查集，几乎是读完题就能下手写的💪，关键是合并策略要写对

代码实现

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int n = s1.length();
        int[] father = new int[26];
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int a = s1.charAt(i) - 'a';
            int b = s2.charAt(i) - 'a';
            merge(father, a, b);
        }
        char[] s = baseStr.toCharArray();
        for (int i = 0; i < s.length; i++) {
            s[i] = (char)(find(father, s[i] - 'a') + 'a');
        }
        return new String(s);
    }

    private int find(int[] father, int a) {
        if (father[a] != a) {
            father[a] = find(father, father[a]);
        }
        return father[a];
    }

    private void merge(int[] father, int a, int b) {
        int fatherA = find(father, a);
        int fatherB = find(father, b);
        if (fatherA >= fatherB) {
            father[fatherA] = fatherB;
        } else {
            father[fatherB] = fatherA;
        }
    }
}

复杂度分析

• 时间复杂度：

  • O(n + m)，其中 n 是 s1/s2 的长度，m 是 baseStr 的长度，并查集的时间复杂度非常接近常数 ✨

• 空间复杂度：

  • O(1) 🎯，因为并查集数组大小固定为26，仅针对小写字母

总结

这道题一看就让人想到并查集，简直就是送分题 🎁。关键在于掌握如何使用并查集合并字符集合，并注意在合并时总是保留字典序最小的字符作为根节点。只要理解并查集的核心思想，实现起来就非常顺手，非常适合作为并查集入门与巩固练习🥰

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。