Java | LeetCode

Задача: 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 {
    int minChar;

    void DFS(int src, Integer[][] adjMatrix, Integer visited[], List<Integer> component) {
        // Mark the character as visited.
        visited[src] = 1;
        // Add it to the list.
        component.add(src);
        // Update the minimum character in the component.
        minChar = Math.min(minChar, src);

        for (int i = 0; i < 26; i++) {
            // Perform DFS if the edge exists and the node isn't visited yet.
            if (adjMatrix[src][i] != null && visited[i] == null) {
                DFS(i, adjMatrix, visited, component);
            }
        }
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        // Adjacency matrix to store edges.
        Integer adjMatrix[][] = new Integer[26][26];
        for (int i = 0; i < s1.length(); i++) {
            adjMatrix[s1.charAt(i) - 'a'][s2.charAt(i) - 'a'] = 1;
            adjMatrix[s2.charAt(i) - 'a'][s1.charAt(i) - 'a'] = 1;
        }

        // Array to store the final character mappings.
        int mappingChar[] = new int[26];
        for (int i = 0; i < 26; i++) {
            mappingChar[i] = i;
        }

        // Array to keep visited nodes during DFS.
        Integer visited[] = new Integer[26];
        for (int c = 0; c < 26; c++) {
            if (visited[c] == null) {
                // Store the characters in the current component.
                List<Integer> component = new ArrayList<>();
                // Variable to store the minimum character in the component.
                minChar = 27;

                DFS(c, adjMatrix, visited, component);

                // Map the characters in the component to the minimum character.
                for (int vertex : component) {
                    mappingChar[vertex] = minChar;
                }
            }
        }

        String ans = "";
        // Create the answer string.
        for (char c : baseStr.toCharArray()) {
            ans += (char)(mappingChar[c - 'a'] + 'a');
        }

        return ans;
    }
}

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

Please open Telegram to view this post