← Static tasks

1202. Smallest String With Swaps

leetcode medium

#array#csharp#graph#leetcode#medium#sort#string

Task

Вам дана строка 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"

C# solution

matched/original
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);
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string SmallestStringWithSwaps(string s, IList<vector<int>> pairs) {
        int n = s.size();
        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]].push_back(pair[1]);
            adj[pair[1]].push_back(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.push_back(node);
            chars.push_back(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.size(); j++) {
                    sArray[indices[j]] = chars[j];
                }
            }
        }
        return new string(sArray);
    }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public String SmallestStringWithSwaps(String s, List<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]);
        }
        boolean[] visited = new boolean[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.size(); j++) {
                    sArray[indices[j]] = chars[j];
                }
            }
        }
        return new String(sArray);
    }
}

JavaScript solution

matched/original
class Solution {
    smallestStringWithSwaps(s, pairs) {
        const adj = Array.from({ length: s.length }, () => []);
        for (const [a, b] of pairs) {
            adj[a].push(b);
            adj[b].push(a);
        }

        const visited = Array(s.length).fill(false);
        const sArray = Array.from(s);

        const dfs = (node, indices, chars) => {
            visited[node] = true;
            indices.push(node);
            chars.push(sArray[node]);
            for (const neighbor of adj[node]) {
                if (!visited[neighbor]) {
                    dfs(neighbor, indices, chars);
                }
            }
        };

        for (let i = 0; i < s.length; i++) {
            if (!visited[i]) {
                const indices = [];
                const chars = [];
                dfs(i, indices, chars);
                indices.sort((a, b) => a - b);
                chars.sort();
                for (let j = 0; j < indices.length; j++) {
                    sArray[indices[j]] = chars[j];
                }
            }
        }

        return sArray.join('');
    }
}

Python solution

matched/original
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        adj = defaultdict(list)
        for a, b in pairs:
            adj[a].append(b)
            adj[b].append(a)
        
        visited = [False] * len(s)
        s = list(s)
        
        def dfs(node, indices, chars):
            visited[node] = True
            indices.append(node)
            chars.append(s[node])
            for neighbor in adj[node]:
                if not visited[neighbor]:
                    dfs(neighbor, indices, chars)
        
        for i in range(len(s)):
            if not visited[i]:
                indices = []
                chars = []
                dfs(i, indices, chars)
                indices.sort()
                chars.sort()
                for index, char in zip(indices, chars):
                    s[index] = char
        
        return ''.join(s)

Go solution

matched/original
import (
    "sort"
)

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    adj := make([][]int, n)
    for _, pair := range pairs {
        adj[pair[0]] = append(adj[pair[0]], pair[1])
        adj[pair[1]] = append(adj[pair[1]], pair[0])
    }

    visited := make([]bool, n)
    sArray := []rune(s)

    var dfs func(node int, indices *[]int, chars *[]rune)
    dfs = func(node int, indices *[]int, chars *[]rune) {
        visited[node] = true
        *indices = append(*indices, node)
        *chars = append(*chars, sArray[node])
        for _, neighbor := range adj[node] {
            if !visited[neighbor] {
                dfs(neighbor, indices, chars)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            indices := []int{}
            chars := []rune{}
            dfs(i, &indices, &chars)
            sort.Ints(indices)
            sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
            for j, index := range indices {
                sArray[index] = chars[j]
            }
        }
    }

    return string(sArray)
}

Explanation

Algorithm

Создание списка смежности:

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

Обход графа и сбор индексов и символов:

Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:

- выполните DFS, если вершина еще не посещена (visited[vertex] = false).

- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

Сортировка и построение результирующей строки:

Отсортируйте списки indices и characters.

Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.

Верните smallestString.

😎