mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
64 lines
2.2 KiB
Markdown
Executable File
64 lines
2.2 KiB
Markdown
Executable File
# [1202. Smallest String With Swaps](https://leetcode.com/problems/smallest-string-with-swaps/)
|
||
|
||
|
||
## 题目
|
||
|
||
You are given a string `s`, and an array of pairs of indices in the string `pairs` where `pairs[i] = [a, b]` indicates 2 indices(0-indexed) of the string.
|
||
|
||
You can swap the characters at any pair of indices in the given `pairs` **any number of times**.
|
||
|
||
Return the lexicographically smallest string that `s` can be changed to after using the swaps.
|
||
|
||
**Example 1:**
|
||
|
||
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"
|
||
|
||
**Example 2:**
|
||
|
||
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
|
||
Output: "abcd"
|
||
Explaination:
|
||
Swap s[0] and s[3], s = "bcad"
|
||
Swap s[0] and s[2], s = "acbd"
|
||
Swap s[1] and s[2], s = "abcd"
|
||
|
||
**Example 3:**
|
||
|
||
Input: s = "cba", pairs = [[0,1],[1,2]]
|
||
Output: "abc"
|
||
Explaination:
|
||
Swap s[0] and s[1], s = "bca"
|
||
Swap s[1] and s[2], s = "bac"
|
||
Swap s[0] and s[1], s = "abc"
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= s.length <= 10^5`
|
||
- `0 <= pairs.length <= 10^5`
|
||
- `0 <= pairs[i][0], pairs[i][1] < s.length`
|
||
- `s` only contains lower case English letters.
|
||
|
||
|
||
## 题目大意
|
||
|
||
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以 任意多次交换 在 pairs 中任意一对索引处的字符。返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
|
||
|
||
提示：
|
||
|
||
- 1 <= s.length <= 10^5
|
||
- 0 <= pairs.length <= 10^5
|
||
- 0 <= pairs[i][0], pairs[i][1] < s.length
|
||
- s 中只含有小写英文字母
|
||
|
||
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 给出一个字符串和一个字符串里可交换的下标。要求交换以后字典序最小的字符串。
|
||
- 这一题可以用并查集来解题，先把可交换下标都 `Union()` 起来，每个集合内，按照字典序从小到大排列。最后扫描原有字符串，从左到右依次找到各自对应的集合里面最小的字符进行替换，每次替换完以后，删除集合中该字符(防止下次重复替换)。最终得到的字符就是最小字典序的字符。
|