1202. Smallest String With Swaps
Вам дана строка 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# решение
сопоставлено/оригинал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++ решение
auto-draft, проверить перед отправкой#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 решение
auto-draft, проверить перед отправкой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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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)
}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.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.