Lexicographically Smallest Equivalent String

给两个字符串, 长度一样, 是字符对应的mapping, 给一个字符串, 求mapping后字典序最小的结果.

典型的并查集模板题.

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) { 
        unionfind uf = new unionfind(26);
        int n = s1.length();
        for(int i = 0; i < n; i++){
            char x = s1.charAt(i);
            char y = s2.charAt(i);
            uf.union((int)(x - 'a'),(int)(y - 'a'));
        }
        StringBuilder sb = new StringBuilder();
        for(char c : baseStr.toCharArray()){
            sb.append((char)('a' + uf.find(c - 'a')));
        }
        return sb.toString();
    }
    
    class unionfind{
        int[] a;
        public unionfind(int n){
            a = new int[n];
            for(int i = 0; i < n; i++)
                a[i] = i;
        }
        public int find(int i) {
            if(a[i] == i)
                return i;
            a[i] = find(a[i]);
            return a[i];
        }
        public void union(int i, int j){
            int x = find(i);
            int y = find(j);
            if(x != y){
                if(x < y)
                    a[y] = x;
                else
                    a[x] = y;
            }
        }
    }
}