C# | LeetCode

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

👨‍💻

Алгоритм:

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎

Решение:

public class Solution {
    public string SmallestStringWithSwaps(string s, IList<IList<int>> pairs) {
        int n = s.Length;
        List<int>[] adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        foreach (var pair in pairs) {
            adj[pair[0]].Add(pair[1]);
            adj[pair[1]].Add(pair[0]);
        }

        bool[] visited = new bool[n];
        char[] sArray = s.ToCharArray();

        void Dfs(int node, List<int> indices, List<char> chars) {
            visited[node] = true;
            indices.Add(node);
            chars.Add(sArray[node]);
            foreach (var neighbor in adj[node]) {
                if (!visited[neighbor]) {
                    Dfs(neighbor, indices, chars);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<int> indices = new List<int>();
                List<char> chars = new List<char>();
                Dfs(i, indices, chars);
                indices.Sort();
                chars.Sort();
                for (int j = 0; j < indices.Count; j++) {
                    sArray[indices[j]] = chars[j];
                }
            }
        }

        return new string(sArray);
    }
}

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

Please open Telegram to view this post