题目描述
给你一个字符串 s
,以及该字符串中的一些索引对
数组 pairs
,其中 pairs[i] = [a, b]
表示字符串中的两个索引(编号从 0 开始)。
你可以 任意多次交换 在 pairs
中任意一对索引处的字符。
返回在经过若干次交换后,s
可以变成的按字典序最小的字符串。
样例
输入:s = "dcab", pairs = [[0,3],[1,2]]
输出:"bacd"
解释:
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
输入: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"
输入: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
中只含有小写英文字母。
算法
(并查集,排序) $O(m + n \log n)$
- 如果我们将索引看做点,将每个索引对看做一条无向边,则这个图可以有若干个连通块,每个连通块内部可以任意排列组合对应的字符。
- 所以我们通过并查集的方式来求出每个连通块,然后在各个连通块内从小到大排序字符,然后再将排序好的字符放回。
时间复杂度
- 遍历数对的时间复杂度为 $O(m)$。
- 并查集的复杂度近似为 $O(n)$。
- 最坏情况下,所有索引在一个连通块内,排序的时间复杂度为 $O(n \log n)$。
- 故时间复杂度为 $O(m + n \log n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间建立并查集,以及构造答案。
- 故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
vector<int> f, sz;
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.length();
f.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) {
f[i] = i;
sz[i] = 1;
}
for (const auto &pr : pairs) {
int fx = find(pr[0]), fy = find(pr[1]);
if (fx != fy) {
if (sz[fx] < sz[fy]) {
f[fx] = fy;
sz[fy] += sz[fx];
} else {
f[fy] = fx;
sz[fx] += sz[fy];
}
}
}
vector<vector<char>> a(n);
vector<vector<int>> pos(n);
for (int i = 0; i < n; i++) {
a[find(i)].push_back(s[i]);
pos[find(i)].push_back(i);
}
for (int i = 0; i < n; i++)
sort(a[i].begin(), a[i].end());
string ans(n, '0');
for (int i = 0; i < n; i++)
for (int j = 0; j < a[i].size(); j++)
ans[pos[i][j]] = a[i][j];
return ans;
}
};