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” এর মত হয়, তাহলে আউটপুট হবে “makkek”। এর কারণ হল A এবং B তে সমতা তথ্যের উপর ভিত্তি করে, আমরা তাদের অক্ষরগুলিকে [m,p], [a,o], [k,r,s], [e,i] হিসাবে গোষ্ঠীবদ্ধ করতে পারি। সুতরাং প্রতিটি গ্রুপের অক্ষরগুলি সমতুল্য এবং আভিধানিক ক্রমে সাজানো হয়েছে। সুতরাং উত্তর হল "মক্কেক"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• অভিভাবক নামে একটি অ্যারে তৈরি করুন

• getParent() নামে একটি পদ্ধতি নির্ধারণ করুন, এটি x

  অক্ষর নেবে

• যদি অভিভাবক [x – 'a'-এর ASCII] -1 হয়, তাহলে 'a'-এর x - ASCII ফেরত দিন

• পিতামাতা [x – 'a' এর ASCII] :=getParent('a' এর ASCII + পিতামাতা[x - 'a' এর ASCII])

• রিটার্ন প্যারেন্ট[x – ASCII of 'a']

• ইউনিয়ন() নামে আরেকটি পদ্ধতি তৈরি করুন, এটি a এবং b

  নেয়

• parentA :=getParent(a), এবং parent :=getParent(b)

• তাই যদি parentA =অভিভাবক, তাহলে ফিরে যান অন্যথায় যখন parentA

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• প্যারেন্ট সেট করুন :=26 আকারের একটি অ্যারে এবং -1

  ব্যবহার করে এটি পূরণ করুন

• আমি 0 থেকে 25 রেঞ্জের জন্য

  • পারফর্ম ইউনিয়ন(A[i], B[i])

• একটি ফাঁকা স্ট্রিং ret তৈরি করুন

• আমি 0 থেকে S

  এর পরিসরে

  • 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