Chuỗi tương đương nhỏ nhất về mặt từ vựng trong C ++

Giả sử chúng ta có các chuỗi A và B có cùng độ dài, bây giờ chúng ta có thể nói A [i] và B [i] là các ký tự tương đương. Vì vậy, ví dụ, nếu A ="abc" và B ="cde", thì chúng ta có 'a' ='c', 'b' ='d' và 'c' ='e'. Các ký tự tương đương tuân theo các quy tắc thông thường của bất kỳ quan hệ tương đương nào:

• Độ phản xạ:'a' ='a'

• Tính đối xứng:'a' ='b' ngụ ý 'b' ='a'

• Độ nhạy:'a' ='b' và 'b' ='c' ngụ ý 'a' ='c'

Ví dụ:với thông tin tương đương từ A và B ở trên, S ="eed", "acd" và "aab" là các chuỗi tương đương và "aab" là chuỗi tương đương nhỏ nhất về mặt từ vựng của S. Ở đây chúng ta phải tìm chuỗi tương đương nhỏ nhất về mặt từ vựng của S bằng cách sử dụng thông tin tương đương từ A và B. Trả lại tất cả các từ có thể được hình thành theo cách này, theo thứ tự từ vựng.

Vì vậy, nếu đầu vào là A =“parker”, B =“morris” và S =“parser”, thì đầu ra sẽ là “makkek”. Điều này là do dựa trên thông tin tương đương trong A và B, chúng ta có thể nhóm các ký tự của chúng thành [m, p], [a, o], [k, r, s], [e, i]. Vì vậy, các ký tự trong mỗi nhóm là tương đương và được sắp xếp theo thứ tự từ vựng. Vì vậy, câu trả lời là "makkek".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng được gọi là mẹ

• Xác định một phương thức có tên getParent (), phương thức này sẽ nhận ký tự x

• nếu cha [x - ASCII của ‘a’] là -1, thì trả về x - ASCII của ‘a’

• cha [x - ASCII of ’a’]:=getParent (ASCII của ‘a’ + cha [x - ASCII của ‘a’])

• trả về cấp độ gốc [x - ASCII của 'a ’]

• Tạo một phương thức khác được gọi là union (), phương thức này nhận a và b

• parentA:=getParent (a) và parent:=getParent (b)

• vì vậy nếu parentA =parent, thì trả về ngược lại khi parentA

• Từ phương thức chính, thực hiện như sau -

• đặt cha:=một mảng có kích thước 26 và điền vào giá trị này bằng -1

• cho tôi trong phạm vi từ 0 đến 25

  • thực hiện liên hiệp (A [i], B [i])

• tạo một chuỗi trống ret

• cho tôi trong phạm vi từ 0 đến kích thước của S

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

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"parker"
"morris"
"parser"

Đầu ra

makkek