<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>

###### tags: `Leetcode`

# 1061. Lexicographically Smallest Equivalent String

###### Link : https://leetcode.com/problems/lexicographically-smallest-equivalent-string

## 題目
找到最小字母順序等效字串
## 程式碼

### Solution

class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<set<char>> char_list(26, set<char>());
        int last=0;
        for(int i = 0; i < s1.size(); i++){
            bool flag = false;
            int locate=0;
            for(int j = 0; j < last; j++){//尋找已存在的set
                if(char_list[j].find(s1[i]) != char_list[j].end()){
                    char_list[j].insert(s2[i]);
                    flag = true;
                    locate = j;
                    break;
                }
                else if(char_list[j].find(s2[i]) != char_list[j].end()){
                    char_list[j].insert(s1[i]);
                    flag = true;
                    locate = j;
                    break;
                }
            }
            if(!flag){//如果沒有找到 新增一個set
                char_list[last].insert(s1[i]);
                char_list[last].insert(s2[i]);
                last++;
            }
            else{
                for(int j = locate+1; j < last; j++){//尋找是否有可連接起來的set
                    if(char_list[j].find(s1[i]) != char_list[j].end() ||
                        char_list[j].find(s2[i]) != char_list[j].end()){
                        for(auto &it : char_list[j]){
                            char_list[locate].insert(it);
                            char_list[j].erase(it);
                        }
                    }
                }
            }
        }
        for(int i = 0; i<baseStr.size();i++){
            for(int j = 0; j < last; j++){
                if(char_list[j].find(baseStr[i]) != char_list[j].end()){
                    baseStr[i] = *char_list[j].begin();
                }
            }
        }
        
        return baseStr;
    }
};

### Better Solution <a href = "https://hackmd.io/s9CujEpmTpW0LNmoqL_klw">(Disjoint Set)</a>

class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        char_list.clear();
        for(char i = 'a'; i <= 'z';i++){
            char_list.push_back(i);
        }
        for(int i = 0;i < s1.size(); i++){
            UNION(s1[i]-'a', s2[i]-'a');
        }
        for(int i = 0;i < baseStr.size(); i++){
            baseStr[i] = find_root(baseStr[i] - 'a') + 'a';
        }
        return baseStr;
    }
private:
    int find_root(int a){
        if(char_list[a] - 'a' == a)
            return a;
        char_list[a] = find_root(char_list[a] - 'a') + 'a';
        return char_list[a] - 'a';
    }
    void UNION(int a, int b){
        int roota = find_root(a);
        int rootb = find_root(b);
        if(rootb < roota)
            char_list[roota] = rootb + 'a';
        else
            char_list[rootb] = roota + 'a';
        return;
    }
    vector<char> char_list;
};