Lexicographically Smallest Equivalent String

문자열 3개를 받는다.

인덱스를 기준으로 s1과 s2는 동일한 문자들로 가정한다.

For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

그리고 동일한 문자들은 아래와 같은 특성들을 가진다

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

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

문제는 쉽게 말하자면 치환이 가능한 문자 집합들을 만들고 baseStr을 가장 작은 문자열로 만들어야 한다.

class Solution {
public:
    static const int ALPHABET_LENGTH = 26;
    int _parent[ALPHABET_LENGTH]{};

    int Find(int x)
    {
        if(_parent[x] == x)
        {
            return x;
        }
        else
        {
            return _parent[x] = Find(_parent[x]);
        }
	}

    void Union(int x, int y)
    {
        x = Find(x);
        y = Find(y);

        if (x == y)
        {
            return;
        }

        if(x < y)
        {
            _parent[y] = x;
        }
        else
        {
            _parent[x] = y;
        }
    }

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        
        for (int i = 0; i < ALPHABET_LENGTH; i++)
        {
            _parent[i] = i;
        }

        int length = s1.size();
        for (int i = 0; i < length; i++)
        {
            Union(s1[i] - 'a', s2[i] - 'a');
        }

        length = baseStr.size();
        for (int i = 0; i < length; i++)
        {
            baseStr[i] = Find(baseStr[i] - 'a') + 'a';
        }

        return baseStr;
    }
};