# 1061. Lexicographically Smallest Equivalent String

{%hackmd theme-dark %}

`s1 = "parker", s2 = "morris"`

Reflexivity: 'a' == 'a'.
Symmetry: 'a' == 'b' implies 'b' == 'a'.
Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

s1[i] s2[i] has properies blow
0:
p <-> m. m==p p==m

aaa
ocb
parker
morris

parser
makkek
s3 ="parser" -> "makkek"

// 1 <= string len <= 1000
// all lowercase char

parker
morris

graph
p: p
a: a

abc
cde

zzz -> zzz

char union_find(unordered_map<char, char> &root, char c) {
    if (root[c] == c) {
        return c;
    }
    
    return union_find(root, root[c]);
}
string parser(string &s1, string &s2, string &s3) {
    unordered_map<char, char> root;
    // set char as it's own root
    for (char c = 'a'; c <= 'z'; c++) {
        root[c] = c;
    }
    // a: a
    // b: b
    // z: z
    
    // construct relationship
    for (int i = 0; i < s1.size(); i++) {
        char root1 = union_find(root, s1[i]);
        char root2 = union_find(root, s2[i]);
        if (root1 < root2) {
            root[root2] = root1;
        } else {
            root[root1] = root2;
        }
    }

    // Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.
    string res;
    for (auto c: s3) {
        res.push_back(union_find(root, c));
    }
    
    return res;
}

        p = {}
        
        def find(x):
            p.setdefault(x, x)
            if x != p[x]:
                p[x] = find(p[x])
            return p[x]
        
        
        for i in range(len(s1)):
            
            gS1, gS2 = find(s1[i]), find(s2[i])
            
            if gS1 == gS2:
                continue
            
            if ord(gS1) < ord(gS2):
                p[gS2] = gS1
            else:
                p[gS1] = gS2

###### tags: `mock interview` `面試`