Сложность: 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.
😎 Решение:
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)
Ставь 👍 и забирай 📚 Базу знаний