lzyprime 博客 (github)
创建时间：2021.01.11
qq及邮箱：2383518170
leetcode 笔记
题目描述
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
code
并查集。 给定[a, b], [b, c] 则 a, b, c 位置可随意调换。所以把连通的全部找出来，每条链排小序。
-
c++
class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int size = s.size();
vector<int> par(size, -1);
for (auto& i : pairs) par[find_parent(par, i[0])] = find_parent(par, i[1]);
unordered_map<int, vector<int>> mp;
for (int i = 0; i < size; i++)
if (par[i] != -1) mp[find_parent(par, i)].push_back(i);
for (auto& i : mp) {
vector<char> tmp;
for (int j : i.second) tmp.push_back(s[j]);
sort(tmp.begin(), tmp.end());
int ti = 0;
for (int j : i.second) s[j] = tmp[ti++];
}
return s;
}
private:
int find_parent(vector<int>& par, int x) {
if (par[x] != -1 && par[x] != x)
return par[x] = find_parent(par, par[x]);
else
return par[x] = x;
}
};
-
kotlin
一刀流。 逻辑复杂，不太适合一刀
fun smallestStringWithSwaps(s: String, pairs: List<List<Int>>): String = String(s.toCharArray().apply { pairs.fold(Array(s.length) { -1 }) { par, i -> par[par.findParent(i[0])] = par.findParent(i[1]);par }.let { par -> par.indices.fold(mutableMapOf<Int, MutableList<Int>>()) { acc, i -> if (par[i] != -1) acc.getOrPut(par.findParent(i)) { mutableListOf() }.add(i);acc } }.forEach { (_, l) -> l.zip(l.map { s[it] }.sorted()).forEach { (i, v) -> this[i] = v } } })
class Solution {
private fun Array<Int>.findParent(x: Int): Int {
if (this[x] != -1 && this[x] != x) this[x] = findParent(this[x]) else this[x] = x
return this[x]
}
fun smallestStringWithSwaps(s: String, pairs: List<List<Int>>): String = String(
s.toCharArray().apply {
pairs.fold(Array(s.length) { -1 }) { par, i ->
par[par.findParent(i[0])] = par.findParent(i[1])
par
}.let { par ->
par.indices.fold(mutableMapOf<Int, MutableList<Int>>()) { acc, i ->
if (par[i] != -1) acc.getOrPut(par.findParent(i)) { mutableListOf() }.add(i)
acc
}
}.forEach { (_, l) ->
l.zip(l.map { s[it] }.sorted()).forEach { (i, v) -> this[i] = v }
}
})
}
-
scala
import scala.collection.mutable
object Solution {
def smallestStringWithSwaps(s: String, pairs: List[List[Int]]): String = {
def find_parent(par: Array[Int], x: Int): Int = {
par(x) = if (par(x) != -1 && par(x) != x) find_parent(par, par(x)) else x
par(x)
}
val par = pairs.foldLeft(Array.fill(s.length)(-1))((par, l) => {
par(find_parent(par, l.head)) = find_parent(par, l.last)
par
})
String.valueOf(
par.indices.foldLeft(mutable.Map[Int, mutable.ListBuffer[Int]]())((mp, i) => {
if (par(i) != -1) mp.getOrElseUpdate(find_parent(par, par(i)), mutable.ListBuffer()).addOne(i)
mp
}).foldLeft(s.toCharArray)((sArray, i) => {
i._2.zip(i._2.map(s(_)).sorted).foreach(i => sArray(i._1) = i._2)
sArray
})
)
}
}
-
Rust
函数式：
use std::collections::HashMap;
impl Solution {
pub fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
let mut s = s.into_bytes();
let size = s.len();
fn find_parent(par: &mut Vec<i32>, x: usize) -> usize {
par[x] = if par[x] != -1 && par[x] != x as i32 {
find_parent(par, par[x] as usize) as i32
} else {
x as i32
};
par[x] as usize
}
let mut par = pairs.iter().fold(vec![-1; s.len()], |mut par, i| {
let pi = find_parent(&mut par, i[0] as usize);
par[pi] = find_parent(&mut par, i[1] as usize) as i32;
par
});
(0..size)
.fold(HashMap::new(), |mut mp, i| {
let v = par[i];
if v != -1 {
mp.entry(find_parent(&mut par, v as usize))
.or_insert(vec![])
.push(i)
}
mp
})
.values()
.for_each(|l| {
l.iter()
.zip({
let mut tmp = l.iter().fold(vec![], |mut acc, &i| {
acc.push(s[i]);
acc
});
tmp.sort();
tmp
})
.for_each(|(&i, v)| {
s[i] = v;
});
});
String::from_utf8(s).unwrap()
}
}
常规写：
use std::collections::HashMap;
impl Solution {
pub fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
let mut s = s.into_bytes();
let size = s.len();
fn find_parent(par: &mut Vec<i32>, x: usize) -> usize {
par[x] = if par[x] != -1 && par[x] != x as i32 {
find_parent(par, par[x] as usize) as i32
} else {
x as i32
};
par[x] as usize
}
let mut par = pairs.iter().fold(vec![-1; s.len()], |mut par, i| {
let pi = find_parent(&mut par, i[0] as usize);
par[pi] = find_parent(&mut par, i[1] as usize) as i32;
par
});
let mut mp: HashMap<usize, Vec<usize>> = HashMap::new();
for i in 0..size {
let v = par[i];
if v != -1 {
mp.entry(find_parent(&mut par, v as usize))
.or_insert(vec![])
.push(i)
}
}
mp.values().for_each(|l| {
let mut tmp: Vec<u8> = l.iter().map(|&i| s[i]).collect();
tmp.sort();
l.into_iter().zip(tmp).for_each(|(&i, v)| s[i] = v)
});
String::from_utf8(s).unwrap()
}
}
