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"