Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium

Даны две строки одинаковой длины s1 и s2, а также строка baseStr.

Мы говорим, что символы s1[i] и s2[i] эквивалентны.

Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.

Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.

Пример:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

👨‍💻 Алгоритм:

1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.

2⃣Итеративно обрабатывайте каждый символ от 0 до 25:

Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.

3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.

😎 Решение:

class Solution {
    void DFS(int src, int[,] adjMatrix, int[] visited, List<int> component, ref int minChar) {
        visited[src] = 1;
        component.Add(src);
        minChar = Math.Min(minChar, src);
        for (int i = 0; i < 26; i++) {
            if (adjMatrix[src, i] != 0 && visited[i] == 0) {
                DFS(i, adjMatrix, visited, component, ref minChar);
            }
        }
    }

    public string SmallestEquivalentString(string s1, string s2, string baseStr) {
        int[,] adjMatrix = new int[26, 26];
        for (int i = 0; i < s1.Length; i++) {
            adjMatrix[s1[i] - 'a', s2[i] - 'a'] = 1;
            adjMatrix[s2[i] - 'a', s1[i] - 'a'] = 1;
        }
        int[] mappingChar = new int[26];
        for (int i = 0; i < 26; i++) {
            mappingChar[i] = i;
        }
        int[] visited = new int[26];
        for (int c = 0; c < 26; c++) {
            if (visited[c] == 0) {
                List<int> component = new List<int>();
                int minChar = 27;
                DFS(c, adjMatrix, visited, component, ref minChar);
                foreach (int vertex in component) {
                    mappingChar[vertex] = minChar;
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        foreach (char c in baseStr) {
            ans.Append((char)(mappingChar[c - 'a'] + 'a'));
        }
        return ans.ToString();
    }
}

Ставь 👍 и забирай 📚 Базу знаний