(LeetCode 每日一题) 1061. 按字典序排列最小的等效字符串 (并查集)

题目：1061. 按字典序排列最小的等效字符串

思路：使用并查集，来将等价的字符连起来，形成一棵树。这棵树最小的字母，就代表整颗树，时间复杂度0(n)，细节看注释。
C++版本：

class Solution {
public:
	// 并查集
    int findd(int u,vector<int> &p){
        if(p[u]!=u) p[u]=findd(p[u],p);
        return p[u];
    }
    string smallestEquivalentString(string s1, string s2, string baseStr) {
    	// 构建并查集的函数
        vector<int> p(26);
        for(int i=0;i<26;i++){
            p[i]=i;
        }
        // 合并等价字母
        for(int i=0;i<s1.size();i++){
            int a=findd(s1[i]-'a',p);
            int b=findd(s2[i]-'a',p);
            //选最小的字母作为根节点
            if(a>b) swap(a,b);
            p[b]=a; 
        }
        // 答案
        string tmp="";
        for(int i=0;i<baseStr.size();i++){
        	// 找到最小的字母下标
            int a=findd(baseStr[i]-'a',p);
            tmp.push_back(a+'a');
        }
        return tmp;
    }
};

JAVA版本：

class Solution {
    int findd(int u,int[] p){
        if(p[u]!=u) p[u]=findd(p[u],p);
        return p[u];
    }
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] p=new int[26];
        for(int i=0;i<26;i++){
            p[i]=i;
        }
        for(int i=0;i<s1.length();i++){
            int a=findd(s1.charAt(i)-'a',p);
            int b=findd(s2.charAt(i)-'a',p);
            if(a>b){
                int t=b;
                b=a;
                a=t;
            }
            p[b]=a;
        }
        char[] s=baseStr.toCharArray();
        for(int i=0;i<s.length;i++){
            s[i]=(char)(findd(s[i]-'a',p)+'a');
        }
        return new String(s);
    }
}

Go版本：

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    p:=make([]int,26)
    for i:=0;i<26;i++ {
        p[i]=i
    }
    for i:=0;i<len(s1);i++ {
        a:=findd(int(s1[i]-'a'),p)
        b:=findd(int(s2[i]-'a'),p)
        if a>b {
            t:=b
            b=a
            a=t
        }
        p[b]=a
    }
    s:=make([]byte,len(baseStr))
    for i:=0;i<len(baseStr);i++ {
        s[i]=byte(findd(int(baseStr[i]-'a'),p)+'a')
    }
    return string(s)
}
func findd(u int, p []int) int {
    if p[u]!=u {
        p[u]=findd(p[u],p)
    }
    return p[u]
}