# 1061. Lexicographically Smallest Equivalent String
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/lexicographically-smallest-equivalent-string/
## 思路
由于需要能找到每个group里面按字母顺序排列最小的那一个
所以每次combine的时候都用字母顺序小的那个当father
这样直接用find函数就可以直接找到这个字符所在group里面字母顺序小的那一个
## Code

class Solution {
    int[] fa;
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        fa = new int[26];
        for(int i=0; i<26; i++){
            fa[i] = i;
        }
        for(int i=0; i<s1.length(); i++){
            combine(s1.charAt(i)-'a', s2.charAt(i)-'a');
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<baseStr.length(); i++){
            sb.append((char)(find(baseStr.charAt(i)-'a')+'a'));
        }
        return sb.toString();
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        if(a<b) fa[b] = a;
        else fa[a] = b;
    }
}