C++에서 사전식으로 가장 작은 등가 문자열

길이가 같은 문자열 A와 B가 있다고 가정하면 이제 A[i]와 B[i]가 동일한 문자라고 말할 수 있습니다. 예를 들어 A ="abc"이고 B ="cde"이면 'a' ='c', 'b' ='d' 및 'c' ='e'입니다. 등가 문자는 모든 등가 관계의 일반적인 규칙을 따릅니다.

• 반사성:'a' ='a'

• 대칭:'a' ='b'는 'b' ='a'를 의미합니다.

• 전이성:'a' ='b' 및 'b' ='c'는 'a' ='c'를 의미합니다.

이제 예를 들어 위의 A와 B의 동등성 정보가 주어지면 S ="eed", "acd" 및 "aab"는 동등한 문자열이고 "aab"는 사전순으로 S의 가장 작은 동등한 문자열입니다. 여기서 우리는 다음을 찾아야 합니다. A와 B의 동등성 정보를 사용하여 사전적으로 가장 작은 S의 동등한 문자열. 이러한 방식으로 형성될 수 있는 모든 단어를 사전순으로 반환합니다.

따라서 입력이 A ="parker", B ="morris" 및 S ="parser"와 같으면 출력은 "mkkek"이 됩니다. 이는 A와 B의 등가 정보를 기반으로 해당 문자를 [m,p], [a,o], [k,r,s], [e,i]로 그룹화할 수 있기 때문입니다. 따라서 각 그룹의 문자는 동일하며 사전순으로 정렬됩니다. 그래서 정답은 "막켁"입니다.

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

• 부모라는 배열을 만듭니다

• getParent()라는 메서드를 정의합니다. 이것은 문자 x를 사용합니다.

• 부모[x – 'a'의 ASCII]가 -1이면 x – 'a'의 ASCII

  를 반환합니다.

• parent[x – 'a'의 ASCII] :=getParent('a'의 ASCII + parent[x – 'a'의 ASCII])

• 반환 부모[x – 'a'의 ASCII]

• Union()이라는 또 다른 메서드를 생성합니다. 이것은 a와 b

  를 취합니다.

• parentA :=getParent(a) 및 parent :=getParent(b)

• 그래서 parentA =parent이면 parentA 를 반환합니다.

• 기본 방법에서 다음을 수행하십시오 -

• set parent :=크기가 26인 배열 및 -1을 사용하여 채우기

• 0에서 25 사이의 i에 대해

  • 합집합 수행(A[i], B[i])

• 하나의 빈 문자열 생성 ret

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

  • ret :=ret + getParent(S[i]) + 'a'

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <int> parent;
   int getParent(char x){
      //cout << x << "-- " << x-'a' << endl;
      if(parent[x - 'a'] == -1) return x - 'a';
      return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
   }
   void unionn(char a, char b){
      int parentA = getParent(a);
      int parentB = getParent(b);
      if(parentA == parentB) return;
      if(parentA < parentB){
         parent[parentB] = parentA;
      }else{
         parent[parentA] = parentB;
      }
   }
   string smallestEquivalentString(string A, string B, string S) {
      parent = vector <int>(26, -1);
      for(int i = 0; i < A.size(); i++){
         unionn(A[i], B[i]);
      }
      string ret = "";
      for(int i = 0; i < S.size(); i++){
         ret += getParent(S[i]) + 'a';
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout <<
   (ob.smallestEquivalentString("parker","morris","parser"));
}

입력

"parker"
"morris"
"parser"

출력

makkek