LeetCode 1061. 按字典序排列最小的等效字符串

Categories:

题目描述
思路分析
1. 解法一：并查集（推荐）
相似题目

题目描述

✅ 1061. 按字典序排列最小的等效字符串

思路分析

解法一：并查集（推荐）

核心思路：

26 个字母建并查集，按位置合并 s1[i] 与 s2[i]。

合并时始终让字典序更小的字母作为根。

对 baseStr 每个字符映射为其集合的最小根。

复杂度分析：

时间复杂度：O(n + m)，其中 n 为 s1 长度，m 为 baseStr 长度。

空间复杂度：O(1)，固定 26 个字母。

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < s1.length(); i++) {
            union(parent, s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < baseStr.length(); i++) {
            int root = find(parent, baseStr.charAt(i) - 'a');
            sb.append((char) (root + 'a'));
        }
        return sb.toString();
    }

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

    private void union(int[] parent, int a, int b) {
        int ra = find(parent, a);
        int rb = find(parent, b);
        if (ra == rb) {
            return;
        }
        if (ra < rb) {
            parent[rb] = ra;
        } else {
            parent[ra] = rb;
        }
    }
}

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    parent := make([]int, 26)
    for i := 0; i < 26; i++ {
        parent[i] = i
    }

    var find func(x int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(a, b int) {
        ra := find(a)
        rb := find(b)
        if ra == rb {
            return
        }
        if ra < rb {
            parent[rb] = ra
        } else {
            parent[ra] = rb
        }
    }

    for i := 0; i < len(s1); i++ {
        union(int(s1[i]-'a'), int(s2[i]-'a'))
    }

    res := make([]byte, len(baseStr))
    for i := 0; i < len(baseStr); i++ {
        root := find(int(baseStr[i] - 'a'))
        res[i] = byte(root) + 'a'
    }
    return string(res)
}

相似题目

题目	难度	考察点
547. 省份数量	中等	并查集
1319. 连通网络的操作次数	中等	并查集
1202. 交换字符串中的元素	中等	并查集
1061. 按字典序排列最小的等效字符串	中等	并查集
721. 账户合并	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/72842458