C++에서 스왑이 있는 가장 작은 문자열

문자열 s와 쌍[i] =[a, b]가 문자열의 2개의 인덱스(0-인덱싱됨)를 나타내는 문자열 쌍의 인덱스 쌍 배열을 제공했다고 가정합니다. 우리는 원하는 만큼 주어진 쌍의 인덱스 쌍에서 문자를 교환할 수 있습니다. 스왑을 사용한 후 변경할 수 있는 사전순으로 가장 작은 문자열을 찾아야 합니다. 따라서 입력이 s ="dcab"이고 쌍 =[[0,3], [1,2]]인 경우 출력은 "bacd"가 됩니다. s[0] 및 s[3], s ="bcad"를 교환한 다음 s[1] 및 s[2], s ="bacd"를 교환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=배열의 크기, 부모 :=크기가 n인 배열을 만들고 -1로 채웁니다.

• 크기가 n인 ret라는 문자열을 만들고 *

  로 채웁니다.

• 범위 0에서 쌍 크기까지의 i에 대해

  • u :=쌍[i, 0] 및 v :=쌍[i, 1]

  • u의 부모가 v의 부모와 같으면 다음 반복으로 건너뜁니다.

  • 부모[u의 부모] :=v의 부모

• 크기가 n인 배열 arr1 정의

• 0 ~ n – 1 범위의 i:arr[i의 부모]

  에 s[i]를 삽입합니다.

• for i in range 0 to n – 1:오른쪽에서 값을 읽어서 arr[i] 정렬

• 0 ~ n – 1 −

  범위의 i에 대해

  • 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"