C ++中带有交换的最小字符串
假设我们给定了一个字符串s，并给定了一个在字符串对中的索引对数组，其中pair[i]=[a，b]表示该字符串的2个索引（0索引）。我们可以根据需要任意多次交换给定对中任意一对索引处的字符。我们必须找到在使用互换之后s可以更改为按字典顺序排列的最小字符串。因此，如果输入类似于s=“dcab”，而对=[[0,3]，[1,2]]，则输出将为“bacd”。交换s[0]和s[3]，s=“bcad”，然后交换s[1]和s[2]，s=“bacd”。
为了解决这个问题，我们将遵循以下步骤-
n：=数组大小，parent：=制作大小为n的数组，并用-1填充
制作一个称为ret的字符串，其大小为n，并用*填充
对于范围在0至成对大小中的i
u：=对[i，0]和v：=对[i，1]
如果u的父级与v的父级相同，则跳到下一个迭代
parent[u的父母]：=v的父母
定义大小为n的数组arr1
对于介于0到n–1之间的i：将s[i]插入arr[i的父项]
对于范围从0到n–1的i：通过从右侧读取值对arr[i]排序
对于i，范围为0到n–1−
ret[i]：=arr1的最后一个[i的父母]
从arr1删除最后一个节点[i的父节点]
范例（C++）
让我们看下面的实现以更好地理解-
class Solution {
public:
vector <int> parent;
int getParent(int x){
if(parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
parent = vector <int>(n, -1);
string ret(n, '*');
for(int i = 0; i < pairs.size(); i++){
int u = pairs[i][0];
int v = pairs[i][1];
if(getParent(u) == getParent(v)) continue;
parent[getParent(u)] = getParent(v);
}
vector < char > arr1[n];
for(int i = 0; i < n; i++){
arr1[getParent(i)].push_back(s[i]);
}
for(int i = 0; i < n; i++){
sort(arr1[i].rbegin(), arr1[i].rend());
}
for(int i = 0; i < n; i++){
ret[i] = arr1[getParent(i)].back();
arr1[getParent(i)].pop_back();
}
return ret;
}
};输入值
"dcab" [[0,3],[1,2]]
输出结果
"bacd"